Greedy algorithms
Define greedy (locally optimal choice, never backtrack), see when greedy is provably optimal, and understand where it fails.
- Define greedy — always make the locally optimal choice and commit to it
- Identify problems where greedy gives a globally optimal solution (interval scheduling, Huffman)
- Explain why greedy fails on 0/1 knapsack
A greedy algorithm makes a sequence of choices where, at each step, it picks the option that looks best right now and never reconsiders it. No backtracking, no global planning, no DP table. When greedy works, it is usually the simplest and fastest correct algorithm. When it fails, a locally attractive choice blocks the globally best solution.
When greedy is optimal
Greedy works when the problem has the greedy-choice property: a locally optimal choice is always part of some globally optimal solution. This is stronger than just "greedy gives a good answer" — it guarantees the answer is exactly right.
Activity selection (interval scheduling maximisation). Given intervals
[start, end], choose the maximum number of non-overlapping intervals.
Greedy: sort by end time, always pick the interval that finishes earliest
and does not overlap the last chosen one.
Why is this correct? The earliest-finishing interval leaves the most room for future intervals. Any globally optimal solution that picks a different first interval can be swapped for the earliest-finishing one without losing ground — this is the exchange argument that proves greedy correctness.
Intervals: [1,4], [3,5], [0,6], [5,7], [8,9], [5,9]
Sorted by end: [1,4], [3,5], [0,6], [5,7], [5,9], [8,9]
Pick [1,4]. Next non-overlapping (start >= 4): [5,7]. Pick.
Next non-overlapping (start >= 7): [8,9]. Pick.
Result: 3 intervals.Huffman coding. Assign shorter bit patterns to more frequent symbols. The greedy step: always merge the two least-frequent nodes. This produces an optimal prefix-free code — provable via exchange argument.
When greedy fails
0/1 knapsack. Items have weights and values; you have a weight capacity. Greedy by value-to-weight ratio sounds reasonable: take the most "efficient" item first. But if the first item fills most of the capacity, you may miss a better combination of smaller items.
Capacity: 10
Item A: weight 6, value 10 (ratio 1.67)
Item B: weight 5, value 8 (ratio 1.60)
Item C: weight 5, value 8 (ratio 1.60)
Greedy takes A (highest ratio), leaving capacity 4 — no room for B or C.
Total value: 10.
Optimal: take B + C, total value 16.Greedy fails here because item A blocks a better combination. The 0/1 constraint (each item taken at most once) means choices interact with each other — exactly the condition under which DP is needed.
A useful mental test: if you can prove that swapping any locally greedy choice for a different one can only worsen the result (the exchange argument), greedy is correct. If you can construct a counterexample where a locally attractive choice leads to a globally worse outcome, use DP.
Where to go next
Next: greedy in practice — two concrete greedy implementations: interval scheduling maximisation and the jump game.