The Exchange Argument

The exchange argument is the most reusable proof technique for greedy algorithms. You assume there is an optimal solution. If that solution already contains the greedy choice, there is nothing to prove. If it does not, you exchange one of its choices with the greedy choice and show that the modified solution remains valid and has objective value no worse than before.

This proves that some optimal solution contains the greedy choice. Once that is established, the algorithm can safely commit to the choice and solve the smaller remaining problem. The proof is often short, but it must address both feasibility and objective value.

Use this template in interviews:

1. Let G be the greedy choice the algorithm makes first.
2. Consider an optimal solution OPT.
3. If OPT already uses G, we are done.
4. Otherwise, identify the item X in OPT that conflicts with or occupies the role of G.
5. Replace X with G.
6. Prove the replacement is feasible.
7. Prove the replacement is no worse for the objective.

The exact meaning of no worse depends on the problem. For maximizing the number of intervals, the count stays the same. For minimizing arrows, the number of arrows does not increase. For lexicographically smallest strings, the resulting string is no larger while still allowing all required future characters.

In maximum non-overlapping intervals, greedy chooses the interval with the earliest end time among all available intervals. Take any optimal solution. If its first interval is not the greedy interval, replace its first interval with the greedy one. The greedy interval ends no later than the original first interval, so every later interval that was compatible before is still compatible after the swap.

The number of chosen intervals is unchanged, and feasibility is preserved. Therefore there exists an optimal solution that starts with the earliest-ending interval. Repeating this reasoning after each choice justifies the full greedy scan.

The first mistake is proving only that the greedy choice looks good, not that it can replace a choice inside an optimal solution. A statement like it leaves more room is useful intuition, but the proof must connect that room to all future choices remaining feasible.

The second mistake is exchanging with the wrong object. In scheduling, the greedy interval usually replaces the first interval of an optimal solution, not an arbitrary later interval. In heap scheduling, a newly considered job may replace the longest accepted job, not necessarily the most recent job. The exchange must target the item whose role the greedy choice can safely take.

The third mistake is ignoring ties. Ties are usually harmless, but the proof should tolerate them. If two choices end at the same time or have the same cost, either can be selected because the exchange remains no worse.