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
jr+1why not replace job jr+1 with job ir+1?
...