Greedy works when a problem has two properties together: optimal substructure and the greedy-choice property.
Optimal substructure
An optimal solution to the whole problem contains optimal solutions to its subproblems. This is shared with dynamic programming and is necessary but not sufficient for greedy.
The greedy-choice property
You can reach a globally optimal solution by making the locally optimal choice at each step without ever reconsidering it. This is the property DP problems lack — in DP, the best choice at a step depends on choices you haven't evaluated yet, so you must try several and keep the best.
When it works — the canonical winners
- Activity selection / non-overlapping intervals — sort by end time, always take the earliest-finishing compatible interval. Provable by exchange argument.
- Huffman coding — repeatedly merge the two lowest-frequency nodes.
- Fractional knapsack — take items by value-per-weight until full (note: the 0/1 version is not greedy — it's DP).
- Dijkstra — greedily finalize the closest unvisited node (works because edge weights are non-negative).
When it fails
- 0/1 knapsack — taking the highest value-per-weight item can lock you out of a better combination; needs DP.
- Coin change with arbitrary denominations —
{1, 3, 4}, target6: greedy gives4+1+1, optimum is3+3. - Longest path, most subset-sum problems — no safe local choice exists.
How to decide in the room
Try to prove the greedy choice is safe with an exchange argument: "swapping any optimal choice for my greedy one doesn't make the solution worse." If you can sketch that, commit to greedy. If you can't — or you can build a small counterexample — fall back to DP. Never ship a greedy heuristic just because it passes the given examples.