A greedy algorithm makes the locally optimal choice at each step and never reconsiders. When the problem has the greedy choice property (a global optimum exists that includes the local greedy choice) and optimal substructure (the remaining problem after that choice is a smaller instance), greedy works. When either fails, greedy gives a wrong answer.
When greedy works
- Interval scheduling: given intervals, pick the maximum number that don't overlap. Greedy: sort by end time, always pick the earliest-ending compatible interval. Provably optimal.
- Huffman coding: build a prefix code by repeatedly combining the two least-frequent characters. Optimal in expected code length.
- Fractional knapsack: items can be split. Greedy: sort by value/weight ratio descending, fill until capacity is exhausted. Optimal because of the fractional element.
- Activity selection, minimum platforms, jump game — all greedy.
When greedy fails
- 0/1 knapsack (no splitting). Highest value/weight ratio doesn't always lead to an optimal selection.
- Coin change with arbitrary denominations. For and amount 6, greedy gives (3 coins) but optimal is (2 coins). DP is needed.
Proof techniques
Two standard ways to argue a greedy is optimal:
1. Greedy stays ahead: at each step, the greedy solution is at least as good as any other partial solution on the same number of items. 2. Exchange argument: take any optimal solution; show you can swap one of its choices with the greedy choice without making it worse.
Recognition
If you can articulate a "best next move" that doesn't require looking ahead, try greedy. Verify with a small test against brute force or DP — if they disagree, greedy isn't valid for this problem.
Greedy vs DP
DP considers all possibilities (cached). Greedy commits to one. When greedy works, it's faster — usually vs DP's or higher. When greedy doesn't work, DP is the fallback. The two often share a recurrence structure; greedy is "the recurrence's max is always at a single fixed branch."