CONCEPT · Novice
Greedy
also exchange argument
Commit to the locally best choice and never revise. Legal only with a proof: exchange argument, matroid, or an obvious stay-ahead.
Intuition
If sorting then taking is correct, you should be able to say why a better solution could be swapped into yours.
When to reach for it
- Scheduling by deadline
- Huffman, Kruskal, Dijkstra's extract-min (with a proof already done for you)
- Some binary-search-on-answer simulations
Usual pits
- Greedy that fails a 4-element counterexample
- Confusing 'looks reasonable' with 'is optimal'