Two ways to prove a greedy algorithm
In the previous guide you watched the "greedy stays ahead" technique work on interval scheduling: we tracked a running quantity (the finishing time of the k-th job) and proved by induction that greedy is never behind any other solution at any step. That argument is powerful, but it needs something to be "ahead" of — a numeric measure that advances cleanly. Many greedy problems do not hand you such a tidy ladder. So this guide builds the other great proof technique, the one that works almost everywhere greedy is correct: the exchange argument.
The idea is disarmingly simple. Suppose, for contradiction, that there is an optimal solution that differs from the greedy one. Find the first place they disagree. At that spot, greedy made some choice and the optimal solution made a different one. The exchange argument says: I can edit the optimal solution — swap its choice for greedy's choice right there — without making it worse. Repeat, and one disagreement at a time the optimal solution morphs into the greedy solution, never losing quality. So the greedy solution is at least as good as that optimal one — which means greedy is optimal too.
A worked swap: minimizing lateness
Let us run the technique on a concrete problem, minimizing maximum lateness. You have one machine and n jobs; job i needs a processing time t_i and has a deadline d_i. You must order all the jobs back to back; if a job finishes at time f, its lateness is max(0, f - d_i). You want to order the jobs so the largest lateness over all jobs is as small as possible. The greedy rule is wonderfully blunt: ignore the processing times entirely and sort the jobs by deadline, earliest deadline first.
To prove this is optimal, define an inversion: a pair of jobs scheduled out of deadline order, meaning a job with a later deadline runs before a job with an earlier deadline. The greedy schedule has zero inversions — that is exactly what "sorted by deadline" means. Take any optimal schedule. If it has no inversions either, it is essentially the greedy schedule already (ties aside) and we are done. Otherwise it has at least one inversion, and here is the key fact you can verify directly: if a schedule has any inversion, it has an inversion between two adjacent jobs.
Now perform the exchange: find an adjacent pair where the earlier-scheduled job has the later deadline, and swap the two. This is the whole move. The beautiful part is what it does to the lateness. The two swapped jobs occupy the same block of time as before, so every other job's finish time — and therefore its lateness — is untouched. Only the two swapped jobs can change, and a short check shows the maximum of their two latenesses does not increase. So one swap removes an inversion and the worst-case lateness never goes up. Keep swapping; each step removes an inversion without harm, and after finitely many steps you reach the zero-inversion greedy schedule. It is no worse than the optimal one you started from, so greedy is optimal.
The shape of every exchange argument
Strip away the scheduling details and the same skeleton appears every time. An exchange argument is really a proof of the greedy-choice property — the claim that some optimal solution contains greedy's first choice — pushed through to the end. Once you have that, optimal substructure does the rest: after fixing greedy's first choice, what remains is a smaller instance of the same problem, and you recurse. The exchange handles "is greedy's choice safe?"; substructure handles "and then the rest is the same problem again." Together they are the two preconditions that make greedy work at all.
- Assume an optimal solution OPT exists that differs from the greedy solution G.
- Locate the first decision where OPT and G disagree (e.g. the first job, or the first adjacent inversion).
- Transform OPT by exchanging its choice there for G's choice, keeping every untouched part frozen.
- Show the exchange does not worsen the objective — the new solution is still optimal (or at least as good).
- Repeat: each exchange strictly reduces the disagreement, so after finitely many steps OPT becomes G — and G is optimal.
Two details in that loop are easy to skip and dangerous to skip. First, the exchange must make measurable progress toward greedy — usually by reducing a count like the number of inversions, or by matching one more of greedy's choices — so that the process terminates after finitely many steps and does not loop forever. Second, "does not worsen" must be argued, not asserted; this is exactly the place where a false greedy rule gets exposed, because the swap that would prove it actually makes some solution worse.
A second flavor: exchange on a sorted order
The inversion-swap above is the classic adjacent-exchange used whenever greedy is "sort by some key, then process in order." The very same idea proves the optimality of the fractional knapsack rule. There greedy sorts items by value-per-unit-weight (the "bang per buck") and pours them into the sack in that order, taking a fraction of the last item if it does not fit whole. To prove it, take an optimal packing that is not the greedy one; somewhere it must include a worse-ratio item while leaving room it could have given to a better-ratio item.
The exchange: shave off a tiny sliver of the worse-ratio item and replace it, by equal weight, with the better-ratio item. Same total weight, so the sack still fits; but because we swapped weight from a low ratio to a high ratio, the total value goes up (or stays equal in a tie). A strictly optimal solution cannot improve, so the swappable situation never existed — the optimal packing must already follow the greedy ratio order. Notice that this swap leans on the items being divisible: you can move "equal weight" of value between them precisely.
That divisibility is not a footnote; it is the whole boundary between greedy working and greedy failing. The instant items become indivisible — you must take each one whole or not at all — you cannot shave a sliver, the exchange breaks, and greedy stops being optimal. This is the gulf between fractional knapsack (greedy is exact) and the 0/1 version (greedy can be arbitrarily bad), which the final guide of this rung explores in full. For now, treat the exchange step itself as a diagnostic: if you cannot construct a value-preserving-or-improving swap toward greedy, that is a loud hint your greedy rule may be wrong.
Honest limits: a swap is not a proof until it is checked
The exchange argument is a recipe, not a guarantee. It only proves a greedy algorithm correct when you can actually carry out two obligations: the swap must never worsen the objective, and the process must terminate. Skip either and you have a story, not a proof. The most common failure is wishful thinking at the "does not worsen" step — people describe a swap, eyeball it, and call it done. The whole point of the local-versus-global distinction is that locally appealing moves can be globally wrong, so this step is precisely where rigor earns its keep.
It is worth saying plainly: "the greedy choice looks best right now" is never, by itself, a proof. A greedy rule can be intuitive, fast, and simply wrong — making coins change for an arbitrary set of denominations is the textbook trap where always grabbing the largest usable coin can use more coins than necessary. The exchange argument is the tool that separates the genuine greedy successes from the impostors, by forcing you to exhibit the swap and verify it preserves optimality. When the swap exists and checks out, you have an airtight inductive proof; when it cannot be built, you have learned something just as valuable.
One more honest note on scope. The exchange argument proves correctness — that greedy returns an optimal answer — and says nothing about running time; a greedy method's speed comes from its sort and its single pass, analyzed separately with the asymptotics from earlier rungs. And when greedy genuinely fails, the exchange's collapse is not a dead end but a signpost: it usually means the problem has no greedy-choice property and you must reach for a method that reconsiders its choices, like the dynamic programming that the next rung builds.