Greedy Algorithms, Dynamic Programming

Interval Scheduling

I really like the notes by Lapchi on this. Very intuitive.

https://cs.uwaterloo.ca/~lapchi/cs341/notes/L11.pdf

Don’t focus on the algorithm, but understanding rather why it is correct. And then, be able to come up with the algorithm fast.

Interval Scheduling

Interval Scheduling Problem

Input: $n$ intervals $[s_1,f_1],[s_2,f_2],...,[s_n,f_n]$. Output: a maximal subset of disjoint intervals.

There are a few greedy ideas that don’t work:

• Choose earliest starting time
  • Counter-example: [1,10], [2,5], [6,8]
• Choose shortest intervals first
  • Counter-example:
• Choose intervals with the minimum number of overlaps first
  • Counter-example:

The proof here is by assuming an optimal solution $O$, and comparing to the output set produced by the greedy algorithm $S$.

And then assume that $|S|<|O|$.

Let $j_r$ be an index into $O$, and $i_r$ be an index into $S$.

At $r=0$, $f(i_r)\le f(j_r)$ (since the greedy algorithm takes interval with the earliest finish time) At Inductive hypothesis: $f(i_{r-1})\le f(j_{r-1})$ $f(j_{r-1})<s(j_r)$ Therefore, $f(i_{r-1})<s(j_r)$

So $j_r$ is an interval that is considered by the greedy algorithm. On the next interval $i_r$ that it selects, it’s either this interval, or an even earlier one. $f(i_r)\le f(j_r)$

Now, let $k$ be the last interval that is in $O$ and $S$. We have $f(i_k)\le f(j_k)$ Since O is bigger, there must exist the interval $j_{k+1}$. we know that $f(j_k)<s(j_{k+1})$

However, we know that $f(i_k)<s(j_{k+1})$ So this interval must be considered by the greedy algorithm. This. is a contradiction.

Weighted Interval Scheduling