Interval Scheduling: AnalysisTheorem. Greedy algorithm is optimal. Pf. (by contradiction) Assume greedy is not optimal, and let's see what happens. Let i1, i2, ... ik denote set of jobs selected by greedy. Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r.
job ir+1 finishes before jr+1
Greedy:
i1
i2
ir
ir+1
OPT:
j1
j2
jr
ir+1
...
solution still feasible and optimal, but contradicts maximality of r.8
