Greedy Algorithms and the Exchange Argument Proof
A greedy algorithm commits to the locally best choice. How to prove one with an exchange argument, activity selection by earliest finish, and when greedy fails.
- Course: Competitive Programming study plan
- Module: Greedy algorithms and exchange proofs
- Kind: Lesson
- Reading time: 14 min
- Runtime: Clang 18 · C++20
What is an exchange argument in a greedy algorithm proof?
An exchange argument proves a greedy algorithm optimal by taking any optimal solution and swapping its choices, one at a time, for the greedy's choices without making it worse. When the optimal solution has been turned into the greedy's solution and never lost value, the greedy's answer must be optimal too. It is the standard way to justify a sort-then-sweep greedy.
Lesson
A greedy algorithm makes the choice that looks best right now and never takes it back. It is the fastest kind of solution — usually a sort and one sweep — and the riskiest, because a plausible rule is often wrong. In a contest you want both halves: the rule, and a reason to believe it.
The recipe
- Guess a rule for the next choice: earliest end, smallest weight, largest ratio.
- Hunt for a counterexample on tiny inputs — on paper, or with a brute force over every subset.
- Prove it with an exchange: take any optimal answer, swap one of its choices for the greedy's, and show nothing got worse.
- Implement: sort by the rule, sweep once. O(n log n).
Activity selection, proved
Choose the most activities [start, end) with no two overlapping. The rule: always take the one that finishes first among those starting after the last one taken.
[1,4) [3,5) [0,6) [5,7) [3,9) [5,9) [6,10) [8,11) [8,12) [2,14) [12,16)- 11 activities, each [start, end), drawn one per lane in order of finishing time. Pick as many as possible with no two overlapping; one may start exactly when another ends.
- The greedy: always take the activity that finishes first among those that start after the last one taken. It takes [1,4), [5,7), [8,11), [12,16): 4 activities.
- Is 4 the best? Take any optimal schedule O, say [3,5), [5,7), [8,12), [12,16) — also 4, sharing only 2 of its activities with the greedy's.
- Swap O's activity 1, [3,5), for the greedy's [1,4). The greedy's ends at 4, no later than 5, so it still finishes before [5,7) starts. Still valid, still 4.
- Swap O's activity 3, [8,12), for the greedy's [8,11). The greedy's ends at 11, no later than 12, so it still finishes before [12,16) starts. Still valid, still 4.
- After the swaps O is exactly the greedy's schedule and never lost an activity. Since O was any optimum, the greedy's 4 is optimal. That is an exchange argument.
Why the swap is safe: the greedy's first pick ends no later than any activity, so putting it in place of O's first one cannot collide with O's second. Repeat for each position and O becomes the greedy's answer without shrinking.
sort(iv.begin(), iv.end(), [](auto& a, auto& b) { return a.second < b.second; });
ll freeAt = LLONG_MIN;
int taken = 0;
for (auto [s, e] : iv)
if (s >= freeAt) { ++taken; freeAt = e; }Rules that look right and are not
- Earliest start: one long activity starting at 0 blocks everything.
- Shortest first: a short activity overlapping two compatible ones costs you one.
- Largest coin first: coins {1, 3, 4}, target 6 → greedy 4+1+1, best 3+3.
The fix for coin change and 0/1 knapsack is dynamic programming. The fractional knapsack is greedy (best value per kilogram first).
The sweep family
Many interval problems are one sort plus one sweep over events:
- Minimum platforms / meeting rooms: turn each interval into +1 at its start and −1 at its end, sort the events, track the running count's maximum. Decide the tie order deliberately — does a train arriving at 10:00 need a fresh platform if another leaves at 10:00?
- Order by a key that the exchange argument picks: sort tasks by duration to maximise "deadline − finish time", because swapping two adjacent tasks out of that order never helps.
More practice
- Non-overlapping Intervals — activity selection, counted the other way.
- Minimum Number of Arrows to Burst Balloons — earliest end again.
- Minimum Number of Platforms — the event sweep.
- Assign Cookies — sort both sides, match greedily.
- Gas Station — a greedy with a one-line proof.
Common questions
How do I know if a greedy algorithm is correct?
Try to prove it with an exchange argument, and try to break it with small counterexamples first. Brute-force every answer for inputs of five or six items and compare with the greedy. If a counterexample appears, the problem probably needs dynamic programming instead.
Why sort activities by end time and not by start time?
Taking the activity that finishes first leaves the most room for everything after it. Sorting by start fails on one long activity that starts first and blocks several short ones; sorting by length fails on a short activity that overlaps two others that would both fit.
When does a greedy algorithm fail?
When a locally best choice can rule out a better combination later. Coin change with coins 1, 3 and 4 and target 6 is the classic case: greedy takes 4 + 1 + 1, three coins, while 3 + 3 uses two. 0/1 knapsack fails the same way.
What is the time complexity of activity selection?
O(n log n) for the sort plus O(n) for one sweep over the sorted activities. The sweep keeps only the end time of the last activity taken.
Exercises
Activity selection
You are given n activities, each a half-open interval [s, e). Choose as many as possible so that no two overlap. An activity that starts exactly when another ends does not overlap it. Print the largest number you can choose.
Input: n (1 ≤ n ≤ 2·10^5), then n lines s e (0 ≤ s < e ≤ 10^9). Output: one integer.
11
1 4
3 5
0 6
5 7
3 9
5 9
6 10
8 11
8 12
2 14
12 16prints
4For example [1,4), [5,7), [8,11), [12,16).
Minimum platforms
n trains use a station. Train i occupies a platform from its arrival a_i to its departure d_i, both inclusive — so a train arriving at the very moment another departs needs a different platform. Print the minimum number of platforms the station needs.
Input: n (1 ≤ n ≤ 2·10^5), then n lines a d (0 ≤ a ≤ d ≤ 10^9). Output: one integer.
6
900 910
940 1200
950 1120
1100 1130
1500 1900
1800 2000prints
3From 1100 to 1120 the trains arriving at 940, 950 and 1100 are all in.
In this module: Greedy algorithms and exchange proofs
← Checkpoint — Binary search on the answer · Checkpoint — Greedy algorithms and exchange proofs →