A pattern for proving greedy
Many greedy algorithms feel obviously right but need a proof to be trusted. The exchange argument is the standard template. It shows that any optimal solution can be transformed into the greedy one, swap by swap, without ever getting worse.
The three moves
A typical exchange proof has a clear shape:
- Assume an optimal solution that differs from the greedy one.
- Find the first place where they disagree.
- Exchange an element of the optimal solution for the greedy choice at that spot, and argue the solution stays valid and no worse.
Repeating the exchange removes every difference one at a time, so the greedy solution is at least as good as the assumed optimal one. Since it cannot be better than optimal, it must be optimal too.
Where it applies
This template proves scheduling rules, the structure of minimum spanning trees, optimal merge orders, and many sorting based greedy methods. The key skill is choosing the right ordering and showing the swap never hurts. If you cannot make a clean swap, that often signals the greedy rule is actually wrong and a counterexample is lurking.
Key idea
An exchange argument morphs any optimal solution into the greedy one through swaps that never hurt, proving the greedy answer optimal.