Exchange arguments, scheduling and greedy proofs

A greedy algorithm makes the locally best choice at each step, without ever revisiting it, and hopes the whole result is optimal. Sometimes it is. An exchange argument is what tells you which: if any optimal solution can be rearranged, one swap at a time, to match what greedy would have chosen, without ever making that solution worse, then the greedy choice was always safe.

The shape of an exchange argument

Say greedy picks option A at some step, while some optimal solution picked option B instead at that same step. An exchange argument shows that swapping B for A inside that optimal solution cannot make it worse. The result is a solution that is still optimal, and now agrees with greedy on that step. Repeating this swap at every point of disagreement turns any optimal solution into the greedy one, without ever losing optimality along the way, which is exactly what it means for the greedy solution to be optimal too.

This style of argument works best on scheduling and selection problems, where the decision at each step is which item to take next, or in what order to take it.

Earliest deadline first

Take a set of tasks, each with a deadline, all needing the same amount of processing time, one time unit each. The goal is to complete as many as possible before their deadlines. Greedy processes tasks in order of deadline, earliest first.

To see why, suppose some schedule processes task x right before task y, but x's deadline is later than y's, the wrong order for earliest-deadline-first. Say x finishes at time t and y finishes at time t + 1. For the schedule to be valid, t must be at most x's deadline, and t + 1 must be at most y's deadline. Swap the two: y now finishes at t, which is even earlier than the t + 1 it already met its own deadline at, so y still meets its deadline. x now finishes at t + 1; since y's deadline is earlier than x's, and t + 1 was already at most y's deadline, t + 1 is also at most x's later deadline. Both tasks still meet their deadlines after the swap, so the swap never makes a valid schedule invalid. Repeating this swap wherever two adjacent tasks are out of deadline order eventually sorts the whole schedule by deadline, without ever breaking a task that was previously on time.

Selecting non-overlapping intervals

Given a set of intervals, each with a start and an end, select as many non-overlapping ones as possible. Greedy sorts by end time and repeatedly takes the earliest-ending interval that does not conflict with what has already been chosen.

If an optimal solution's first interval is not the one greedy would pick, swap it for the greedy choice, the interval that ends earliest of all. Since that interval ends no later than the one it replaced, everything the optimal solution chose after its own first interval still avoids conflict with this earlier-ending replacement, since ending earlier only ever loosens a non-overlap constraint, never tightens it. The same swap applies at the next step, and the one after, until the whole solution matches greedy's choices, without ever having removed an interval from the count.

A worked example

Five tasks, with deadlines: A at 3, B at 1, C at 4, D at 2, and E at 2. Sorted by deadline: B, D, E, A, C.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    if not data:7        return8
9    # Parse tasks and deadlines10    n = int(data[0])11    tasks = []12
13    for i in range(n):14        deadline = int(data[1 + i])15        tasks.append((deadline, f"Task{chr(65 + i)}"))16
17    # Sort by deadline (greedy: earliest deadline first)18    tasks.sort()19
20    completed = []21    current_time = 122
23    for deadline, name in tasks:24        if current_time <= deadline:25            completed.append(name)26            current_time += 127
28    print(f"Completed {len(completed)} tasks: {', '.join(completed)}")29
30
31if __name__ == "__main__":32    main()

5 3 1 4 2 2

Completed 4 tasks: TaskB, TaskD, TaskA, TaskC

Processing in that order: B finishes at time 1, meeting its deadline of 1. D finishes at time 2, meeting its deadline of 2. E would finish at time 3, missing its deadline of 2, so it is skipped. A finishes at time 3, meeting its deadline of 3. C finishes at time 4, meeting its deadline of 4. Four of the five tasks complete, B, D, A, and C, which the exchange argument above guarantees is the best any schedule can do.

When greedy fails

Not every version of a problem admits a greedy solution, and the exchange argument is exactly what tells you whether one is available before you commit to a greedy approach. Change the deadline-scheduling problem so each task also carries a value, and the goal becomes maximizing total value rather than task count. Sorting by deadline alone stops being optimal, since a schedule might skip a low-value task with an early deadline to fit two high-value tasks with later ones. This version needs dynamic programming instead, not a greedy rule.

The traveling salesman problem is another case where no exchange argument exists for the obvious greedy rule. Repeatedly visiting the nearest unvisited city can lock you into a long detour later, and no sequence of local swaps turns every optimal tour into the one that rule would have produced.

Where exchange arguments show up

An exchange argument, once it holds, is a proof, not just a pattern that happened to work on a few test cases. Dijkstra's shortest paths algorithm is greedy by distance, Kruskal's minimum spanning tree algorithm is greedy by edge weight, and Huffman coding is greedy by frequency; each of these has its own exchange argument establishing that the greedy rule always reaches an optimal answer, not merely a good one.

Recap

An exchange argument proves a greedy algorithm optimal by showing that any optimal solution disagreeing with it can be rearranged, one swap at a time, to match it without ever getting worse. Earliest-deadline-first scheduling and earliest-end-time interval selection both have exchange arguments behind them. Where no such argument exists, as with value-weighted scheduling or the traveling salesman problem, greedy needs to be replaced with a technique that actually accounts for the trade-offs involved.