Exchange Arguments and Counterexamples
Proving greedy correct with the exchange argument; building counterexamples when it is wrong; the staying-power rule for beginners.
Two habits separate guessing from proving
When greedy works, say why in one sentence
- Coin change (canonical): "taking the largest coin never forces more coins later" — exchange argument.
- Meetings by end time: "the earliest-finishing choice dominates" — any optimal solution can be rewritten to include it.
- Minimum total waiting time: serve shortest jobs first (SPT) — swapping an earlier long job with a later short job never increases total wait.
When it fails, the counterexample is tiny
The denomination system 4 kills naive coin greedy at amount 6. When a problem smells greedy but you doubt the strategy, hunt small: try n = 2, 3, 4 by hand before coding anything.
The beginner's safety rule
If you cannot produce either a one-sentence exchange argument or a counterexample, you are guessing. In a 180-minute exam, a wrong greedy costs the full problem. When in doubt for small n, a brute-force or DP fallback earns subtask points (partial scoring!) that a wrong greedy earns zero.
Sorting is the greedy prelude
Most beginner greedy problems are sort first, sweep second:
| Sort key | Classic problem | | --- | --- | | end time | meeting-room maximization | | right endpoint | interval point-cover | | ratio value/weight | fractional knapsack | | deadline | job scheduling with deadlines |