Card 04/ 08
Proving a Greedy Choice With an Exchange Argument
Take any best schedule, swap its first meeting for the greedy one, and show nothing got worse.
An exchange argument proves a greedy rule correct by starting from any best solution and swapping its choices, one at a time, for the greedy ones, showing that each swap keeps the solution valid and no worse. This card runs the argument for earliest-finish scheduling on the six meetings from Schedule the Most Meetings by Earliest Finish.
The argument has three parts. The swap stays valid: replacing a choice with the greedy one breaks no rule. The swap costs nothing: the solution is as good afterwards as before. And repeating the swap turns the best solution into the greedy one, which must therefore be best too. It never needs to know which best solution it started from, which is what makes it a proof rather than a check of one case.
Each step below shows the schedule on a time axis from 0 to 10, one bar per meeting, printed by a run that made the swaps and checked that no two bars overlap.
Turning a best schedule into the greedy one, one swap at a time
The greedy schedule
The greedy rule keeps A, C and F, three meetings.
greedy
0 1 2 3 4 5 6 7 8 9 10
A [=========]
C [==============]
F [=========]Any best schedule
Suppose someone hands you a different schedule of three meetings, B, D and F, and claims it is best. Nothing overlaps: B ends at 5, before D starts at 6, and D ends at 8, when F starts.
best
0 1 2 3 4 5 6 7 8 9 10
B [==============]
D [=========]
F [=========]Swap the first meeting
The greedy first choice is A, the meeting that ends earliest of all, so A ends no later than B. Replace B with A. Everything after B started after B ended, at 5 or later, so it starts after A ends at 3 too. The run confirmed the schedule is valid and still holds three meetings.
swap B for A
0 1 2 3 4 5 6 7 8 9 10
A [=========]
D [=========]
F [=========]Swap the second meeting
Now the schedules agree on the first meeting, and the same argument applies to what is left: among the meetings that start after A ends, the greedy rule picks C, which ends earliest, at 7. D ends at 8, so C ends no later, and F still starts after it. Replace D with C: valid, and still three meetings.
swap D for C
0 1 2 3 4 5 6 7 8 9 10
A [=========]
C [==============]
F [=========]The schedules agree
The third meeting is F in both, so no swap is needed, and the best schedule has become the greedy one without losing a meeting. Had the best schedule held more meetings than the greedy one, the greedy rule would have found room for the extra one after its last choice, since that choice ends no later than the best schedule's. So no schedule beats the greedy one.
The swap in each step relied on one fact: the greedy choice finishes no later than the choice it replaces. That fact is the greedy choice property for this problem, and the step after each swap, applying the same argument to the meetings that are left, is optimal substructure.
The same three parts prove other greedy rules. For the jobs on Choosing the Key a Greedy Algorithm Sorts By, the swap exchanges two neighbouring jobs that are out of deadline order and shows the worst lateness does not rise. When a swap does make the solution worse, the exchange argument fails, and the failed swap usually points straight at a counterexample.
← → move through sections and cards