Greedy algorithms

Make the locally-best choice, never look back. Works only for the RIGHT criterion — which needs a proof.

Interval scheduling: which greedy?

• Fit the most non-overlapping activities in one room
• Earliest START? Earliest FINISH? SHORTEST? All plausible.
• Only earliest FINISH is optimal
• Finishing early leaves the most room for what follows

Watch the earliest-finish sweep

Sorted by finish time; dashed line = last taken finish (room free to its right). Take if it starts after the line; skip if it overlaps. → 4 activities, the max.

The criterion is everything

Earliest-finish: optimal. Earliest-start: ~40% worse. Shortest: 13.0 vs 13.1 — looks right, isn't.

Prove it, don't benchmark it

• Correctness = worst case over ALL inputs; one counterexample kills it
• Shortest-first fails on [0,10),[9,11),[10,20): picks 1 where optimum picks 2
• Exchange argument: swap the optimum's choice for the greedy one, no worse
• Edmonds: greedy is optimal exactly on matroids

Takeaway

Simplest to write, easiest to get subtly wrong. A greedy that's usually right is still a bug. Next: dynamic programming — for the overlapping-subproblem cases greedy can't touch.