The greedy method
When taking the locally best choice is globally optimal — and how to prove it. · 11 min read
Concept
A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now, and never undoing it. It's the simplest strategy there is — the hard part isn't coding it, it's knowing when it actually gives the optimal answer.
Two properties greedy needs
- Greedy-choice property: a globally optimal solution can be reached by making locally optimal choices. The first greedy choice is always part of some optimal solution.
- Optimal substructure: after making the greedy choice, the remaining subproblem is the same kind of problem, and combining its optimal solution with the greedy choice is optimal.
Activity selection
The classic example: given activities with start/finish times, attend the most activities without overlap. The greedy rule is to repeatedly take the activity that finishes earliest among those still compatible — finishing early leaves the most room for the rest.
Interactive visualization: Sort by finish time, then take non-overlapping activities — step through it frame by frame on this page.
Why it's optimal — the exchange argument
Let g be the activity that finishes first.— Greedy picks it.Take any optimal solution O; let o be its first activity.— o finishes no earlier than g.Swap o for g in O.— g finishes ≤ o, so it still doesn't overlap the rest — the set stays valid and the same size.So an optimal solution contains the greedy choice; recurse on the rest.— By induction, greedy is optimal.
Result: Greedy = optimal for activity selection
When greedy fails
Greedy is not a universal hammer. For 0/1 knapsack, taking the highest value-per-weight item first can be wrong — you might fill the bag with one efficient item and waste the rest. That problem needs dynamic programming. Always justify greedy with an exchange argument (or a counterexample to kill it).
Practice: Activity Selection (Easy) — Max non-overlapping intervals — take earliest finish each time.
Practice: Jump Game (Medium) — Can you reach the last index? Track the furthest reachable point.