Algorithms from zero
The Exchange Argument: proving a greedy choice is safe
Last lesson you wrote greedy algorithms that grab the locally best option at each step and never look back. They were fast and simple—but “simple” is not the same as “correct.” Sometimes that greedy grab paints you into a corner and the final answer is worse than the best possible. So how do you ever trust a greedy algorithm? You do not run it on a few inputs and hope. You prove it. The workhorse proof is the exchange argument: take any optimal solution, show you can nudge it one step toward what greedy picks without making it worse, and conclude that a greedy-aligned optimum must exist. This lesson teaches you that proof—and how to spot when it fails.
After this lesson you can prove a greedy algorithm correct with the exchange argument: assume an optimal solution that differs from the greedy one at the first choice, then exchange that part of the optimum for the greedy choice and show the result is still feasible and no worse. You can run this argument concretely on activity selection (pick the earliest-finishing compatible job) and explain why the swap never reduces how many jobs you fit. You can name the two halves a full greedy proof needs—the exchange argument for the safe first choice plus optimal substructure for the rest—and you can recognize the sibling technique, “greedy stays ahead,” which tracks a single quantity instead of swapping. Crucially, you can show when the exchange argument fails: the coin system 4 has no valid swap, and that missing swap is exactly why greedy is wrong there. Next lesson applies these tools to a classic greedy problem end to end.
Why a greedy algorithm needs a proof at all
A greedy algorithm commits to the locally best option at every step. The danger is obvious: a choice that looks best right now might block a better choice later. So before you trust greedy on a problem, you must prove its first choice is safe—that committing to it never costs you the optimal answer. The exchange argument is how you prove exactly that.
The exchange argument, in three moves
You want to show: there exists an optimal solution that agrees with the greedy choice. The proof is a thought experiment, not code.
- Assume an arbitrary optimal solution
O. Maybe it already makes the greedy first choice—then you are done. So assume it does not:Ois optimal but differs from greedy at the first decision. - Exchange. Modify
Oby swapping out whatever it chose first and swapping in the greedy choice, producing a new solutionO'. The whole craft is designing this swap soO'is still feasible (a valid solution) and no worse thanO(same value, or better). - Conclude. Since
Owas optimal andO'is no worse,O'is also optimal—andO'now agrees with greedy on the first choice. So an optimal solution containing the greedy choice exists. The greedy first choice is safe.
Repeat the same reasoning on the smaller problem that remains after the first choice (this is optimal substructure), and by induction the entire greedy solution is optimal.
Optimal O : [ X ] rest... (X = what O chose first, not greedy's pick)
| swap X -> G
v
New O' : [ G ] rest... same size / value, still feasible
^
greedy's choice G now sits in an optimal solution -> G is safeThe key insight: you do not build greedy’s answer—you reshape the optimum toward it
Notice the direction. You are not arguing greedy is best from scratch. You start from a known optimum and transform it one swap at a time until it looks like greedy’s output, proving at each swap that nothing was lost. If every swap is harmless, greedy’s output is as good as the optimum.
A worked target: activity selection
You have jobs, each with a start and finish time. You want the most jobs that do not overlap. The greedy rule: always pick the compatible job that finishes earliest. Intuition: finishing earliest leaves the most room for everything after it. The exchange argument makes that intuition rigorous.
Let G be the earliest-finishing job overall, and let O be any optimal schedule. Let X be the first job in O (the one that finishes earliest in O). Because G finishes earliest of all jobs, G.finish <= X.finish. Swap X out of O and G in:
- Still feasible? Yes.
Xwas compatible with the rest ofO, meaning everything else inOstarts at or afterX.finish. SinceG.finish <= X.finish, those same jobs also start at or afterG.finish. SoGdoes not overlap any of them. - No worse? Yes. We removed exactly one job and added exactly one job: the count is unchanged.
O'schedules just as many jobs asO.
So O' is optimal and contains G. The greedy first pick is safe. Strip G and the jobs it conflicts with, and the leftover is a smaller activity-selection problem—solve it the same way. Greedy is optimal.
The sibling technique: “greedy stays ahead”
The exchange argument swaps inside the optimum. “Greedy stays ahead” instead tracks one measurable quantity and proves greedy’s value is, at every step, at least as good as any other solution’s. For activity selection you would prove: after picking its first k jobs, greedy’s k-th job finishes no later than any other valid schedule’s k-th job—so greedy never falls behind and ends up fitting at least as many jobs. Both techniques prove the same correctness; pick whichever is cleaner for the problem. Exchange tends to be the more general tool.
When the exchange argument fails, greedy is wrong
The argument is not a rubber stamp—it only works when a harmless swap actually exists. If you cannot swap the optimum toward the greedy choice without making it worse, that is not a gap in your cleverness; it is a proof that greedy is unsafe. The coin system 4 making change for 6 is the classic failure: greedy grabs the 4, then needs 1 + 1, for 3 coins—but the optimum is 3 + 3, just 2 coins. Try to swap the optimum’s pair of 3s toward greedy’s 4 and you are stuck: removing a 3 and adding a 4 overshoots. No valid exchange exists, so greedy is not provably optimal here—and indeed it is wrong.
The greedy activity-selection algorithm
The proof above justifies a tiny algorithm: sort jobs by finish time, then walk left to right taking every job that starts at or after the last one you took finished.
1
function selectActivities(jobs) {
2
// Greedy rule: consider jobs in order of earliest finish time
3
const byFinish = [...jobs].sort((a, b) => a.finish - b.finish);
4
const chosen = [];
5
let lastFinish = -Infinity; // finish time of the last job we took
6
for (const job of byFinish) {
7
// Compatible if it starts at or after the last chosen job ended
8
if (job.start >= lastFinish) {
9
chosen.push(job.name); // safe greedy pick (exchange argument)
10
lastFinish = job.finish; // advance the boundary
11
}
12
}
13
return chosen;
14
}
- L3 Sort by finish time. Earliest finish first is exactly the choice the exchange argument proved safe.
- L5 lastFinish is the wall: the moment the previously chosen job ended. Starts at -Infinity so the first job always qualifies.
- L8 Compatibility test: a job is allowed only if it starts at or after the last one finished (no overlap).
- L9 Take it. By the exchange argument, an optimal schedule containing this earliest-finishing compatible job exists.
- L10 Move the wall forward to this job's finish, then keep scanning the rest.
Key point: the proof is what lets you stop thinking
The code never reconsiders a choice—no backtracking, no comparing alternatives. That confidence comes entirely from the exchange argument: every pick is safe, so the single left-to-right pass is guaranteed optimal. Without the proof, this code would just be a hopeful heuristic.
Running it: greedy finds the maximum set
Greedy takes A (finishes at 4), then D (starts at 5, after 4), then H (starts at 8, after 7), then K (starts at 12, after 11): four non-overlapping jobs. No schedule fits more—the exchange argument is why we can claim that without checking every possible subset.
The contrast: where no exchange exists
The same “grab the biggest fitting piece” greedy works for some coin systems and fails for others. The code below runs greedy against the true optimum (found by exhaustive dynamic programming) for the 4 system. The mismatch is the fingerprint of a missing exchange.
Greedy uses 3 coins (4 + 1 + 1); the optimum is 2 (3 + 3). There is no way to swap the optimum’s two 3s toward greedy’s 4 without breaking it, so the exchange argument refuses to go through—and the algorithm is wrong. The proof technique correctly predicts the failure.
Let us trace the exchange argument itself on activity selection. We start from a hypothetical optimal schedule O that does NOT begin with the earliest-finishing job, then perform the swap and watch nothing get worse. Jobs: G=[0,3] (earliest finish), X=[1,4], P=[4,6], Q=[6,9]. Suppose O = {X, P, Q}—three jobs, optimal—but it skipped G.
1
// Optimal O does not start with greedy's job G
2
O = [ X , P , Q ] // X finishes at 4
3
G.finish (3) <= X.finish (4) // G finishes no later
4
swap: remove X, insert G
5
O' = [ G , P , Q ] // still no overlaps?
6
count(O') == count(O) // no worse
The proof costs nothing at runtime
The exchange argument is reasoning you do once, on paper, before you ship. It does not run. What runs is the algorithm it justifies—and that algorithm is cheap precisely because the proof removed any need to reconsider choices.
Activity-selection runtime: O(n log n)
sort jobs by finish time -> O(n log n)
single left-to-right scan -> O(n)
total -> O(n log n), dominated by the sortThere are n jobs. Sorting by finish time is the only expensive step at O(n log n); the greedy scan visits each job once, doing O(1) work per job (one comparison, maybe one push), for O(n). The total is O(n log n). Space is O(n) for the sorted copy and the chosen list, or O(1) extra if you sort in place and only count the result.
Why the proof matters for cost
Contrast this with brute force: checking every subset of jobs for the largest non-overlapping one is O(2^n). The exchange argument is what collapses that exponential search into one sorted pass. The proof is not a formality—it is the entire reason the fast algorithm is allowed to exist. A greedy rule with no valid exchange (like 4 coins) gives a fast wrong answer; the proof is the line between fast-and-correct and fast-and-wrong.
Reading the failure cost
In the coin demo, the exhaustive optimalCoins DP runs in O(amount x coins)—we only used it to expose greedy’s mistake, not as the real algorithm. The lesson there is diagnostic: when greedy and a known-correct method disagree on even one input, the exchange argument was never going to close, and you must use DP (or another exact method) instead.
What is the exchange argument trying to prove about a greedy algorithm?
In the exchange argument, after you swap part of an optimal solution O toward the greedy choice, what two properties must the new solution O' have?
For activity selection, why does swapping the greedy job G in for O's first job X keep the schedule feasible?
Greedy on the coin system {1, 3, 4} makes change for 6. What happens, and what does it reveal?
How does the 'greedy stays ahead' technique differ from the exchange argument?
A full greedy correctness proof usually has two parts. What are they?
Run the greedy activity selector on the 11 jobs from the code example. How many non-overlapping jobs does it choose?
Why this works
Why “no worse” instead of “strictly better”? The exchange argument only needs the swapped solution O' to be as good as the optimum O, not better. If you could always make it strictly better, then O was not optimal to begin with—a contradiction, which is fine but unnecessary. The honest claim is gentler: the greedy choice never costs you anything. Since O was optimal and O' matches its value, O' is also optimal and now contains the greedy choice. “No worse” is exactly the right strength: strong enough to prove safety, weak enough to actually hold.
Common mistake
Mistake: assuming greedy is right because it worked on your examples. Passing three test inputs proves nothing about optimality—the 4 coin greedy is correct for amounts 1 through 5 and only breaks at 6. A greedy heuristic can be right on a thousand inputs and wrong on the thousand-and-first. The only trustworthy verdict comes from a proof (an exchange argument or “stays ahead”) or, when no proof closes, from a counterexample that disproves it. “It seems to work” is the single most expensive assumption in greedy design.
Edge cases
When the swap is harmless but the choice is not the greedy one. Some problems have multiple optimal first choices—ties. The exchange argument still works: you only need one optimal solution that agrees with greedy, not that every optimum does. In activity selection, if two jobs finish at the same earliest time, picking either is safe, and the swap (G.finish <= X.finish) holds with equality. Ties never break the argument; they just mean greedy had more than one safe move available.
More practice
The recipe for proving a greedy algorithm. (1) State the greedy rule precisely (e.g. “earliest finish time”). (2) Take an arbitrary optimal O; if it already follows the rule’s first choice, done—else it differs at the first step. (3) Design the swap: replace O’s differing part with the greedy choice to get O'. (4) Prove O' is feasible and no worse than O. (5) Invoke optimal substructure: recurse on the smaller remaining problem. If step 3 or 4 cannot be done, search for a counterexample instead—greedy is probably wrong. Try this recipe on “schedule jobs to minimize maximum lateness” next.
Explain the exchange argument: what it proves, the three moves, why activity selection's swap is valid, the sibling 'stays ahead' technique, and what a failed exchange means.
A greedy algorithm is only correct if its first choice is safe, and the exchange argument is how you prove safety.
The three moves:
- Assume an arbitrary optimal
Othat differs from greedy at the first choice. - Exchange
O’s differing part for the greedy choice, producingO'that is still feasible and no worse thanO. - Conclude
O'is optimal and contains the greedy choice—so the greedy first choice is safe.
The direction that matters: you do not build greedy’s answer from nothing; you reshape a known optimum toward it, one harmless swap at a time.
Activity selection (pick the earliest-finishing compatible job): the swap is valid because greedy’s G finishes no later than O’s first job X (G.finish <= X.finish), so every later job still fits and the count never drops. Runtime is O(n log n), dominated by sorting on finish time.
Two halves of a full proof: the exchange argument (safe first choice) plus optimal substructure (the rest is a smaller instance), tied together by induction. The sibling “greedy stays ahead” proves the same thing by tracking one quantity and showing greedy never falls behind.
When the exchange fails, greedy is wrong: coins 4 for amount 6 give greedy 3 coins (4+1+1) versus the optimal 2 (3+3). No harmless swap exists, and that missing swap is the proof that greedy is unsafe—a counterexample, not a coding bug.
Next: a classic greedy problem worked end to end, using the exchange argument to justify every choice.