The exchange argument

Greedy algorithms are the cheapest correct solutions in the catalogue and the most common wrong ones. Sort by something plausible, take whatever fits, and you have ten lines that run in O(n log n) — code that is either optimal or arbitrarily bad, with nothing on the page to tell you which.

The thing that separates the two is a proof. Greedy has two standard ones — greedy stays ahead, which shows greedy's prefix is never behind a rival's after k steps, and the exchange argument, which is the one you can always reach for. It is short enough to say out loud in thirty seconds, which is why an interviewer expects to hear it every time.

The argument has a fixed skeleton

Let G be the solution greedy builds and O be any optimal solution.

1. Find the first place where G and O differ.
2. Show that replacing O's choice at that point with greedy's choice leaves a solution that is still valid and no worse.
3. The modified O agrees with G one step further along. Repeat until O has become G. Nothing was lost at any step, so G is optimal too.

Steps 1 and 3 are bookkeeping. Step 2 is the argument, and it is where a wrong greedy rule dies: you try to construct the swap, and find it makes the answer worse.

Activity selection, done properly

Five activities as half-open intervals; you want the largest non-overlapping set:

Activity	Interval	Finishes
a	[1, 4)	4
b	[3, 5)	5
c	[0, 6)	6
d	[5, 7)	7
e	[8, 9)	9

The greedy rule is earliest finishing time: sort by finish, then walk the list taking any activity that starts at or after the last finish you committed to.

def select(activities):
    """activities: list of (start, finish). Returns a largest non-overlapping set."""
    chosen, last_finish = [], float("-inf")
    for start, finish in sorted(activities, key=lambda x: x[1]):
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen

Sorted by finish: a, b, c, d, e. Take a, clock to 4. Skip b (starts at 3) and c (starts at 0). Take d, clock to 7. Take e. Result {a, d, e}, three activities.

Now the proof. Take any optimal set O in start order and let x be its first activity. Greedy's first pick g finishes no later than any activity, so finish(g) ≤ finish(x). Swap them: O with g in place of x is still non-overlapping, because O's second activity starts at or after finish(x), which is at or after finish(g). Same size, so still optimal. Every remaining activity now starts at or after finish(g) — the identical problem on a shorter list, so the argument repeats for the second pick, the third, and greedy is optimal.

Swapping the earliest-finishing activity into an optimal schedule without shrinking it100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The obvious alternative rule fails on this same list. Sort by earliest start and you take c first, which alone blocks a, b and d — you end with {c, e}, two activities against the optimum of three. That failure is not bad luck; it is the exchange argument refusing to go through, because swapping c into an optimal set can evict two activities to admit one.

Where the same move fails: 0/1 knapsack

Capacity 10, and three indivisible items:

Item	Weight	Value	Value per unit weight
A	6	12	2.0
B	5	9	1.8
C	5	9	1.8

The obvious greedy takes the best ratio first. It takes A for 12, leaving capacity 10 − 6 = 4, and neither B nor C fits in 4. Total: 12.

The optimum is B and C: weight 5 + 5 = 10, exactly full, value 9 + 9 = 18. Greedy lands 6 short, 12 ÷ 18 ≈ 67% of optimal — and no bound you can quote here, because scaling the same shape makes the ratio as bad as you like.

Watch step 2 collapse. To exchange A into the optimal set {B, C} you need 6 units of room. Dropping B frees 5, not enough; you must drop B and C, trading 18 for 12. The swap is available and it makes the answer strictly worse, so the proof does not exist, and for a structural reason: with indivisible items, admitting one greedy item can cost you two, and no per-item comparison sees that coming.

Make the items divisible and the obstruction vanishes: take all of A (12) plus 4/5 of B (0.8 × 9 = 7.2) for 19.2, and the exchange goes through, because any unit of weight in O with a worse ratio can be swapped for a unit of the greedy item. Divisibility is not a detail of the problem statement; it is the precondition that licenses the proof.

For 0/1 the honest answer is a table over capacities (that lesson calls the capacity C):

def knapsack(items, cap):
    """items: list of (weight, value). Returns the best value within cap."""
    best = [0] * (cap + 1)
    for weight, value in items:
        for c in range(cap, weight - 1, -1):
            best[c] = max(best[c], best[c - weight] + value)
    return best[cap]

What the proof costs you

Greedy on the activity list is one sort. At n = 10⁵ that is roughly n log₂ n ≈ 10⁵ × 17 ≈ 1.7 million operations — well under a second at the ~10⁸ simple operations per second used in complexity by counting.

The knapsack DP is O(n × W). With n = 100 items and capacity W = 10⁵ that is 100 × 10⁵ = 10⁷ cells, about 0.1 s. Greedy on the same input would be 100 × log₂100 ≈ 700 operations, roughly 14,000× cheaper — and wrong by a third on a three-item instance. That table is also pseudo-polynomial: it tracks W's magnitude, not its digit count, so W = 10⁹ makes it impossible while the input barely grows.

In an interview

The interviewer is testing whether you can tell a proof from a coincidence. Greedy problems are set precisely because the plausible rule and the correct rule both pass the sample input, so passing the sample earns nothing.

Say the argument in this form: "Greedy takes the earliest-finishing activity. Take any optimal solution; its first activity finishes no earlier than mine, so I can swap mine in without breaking feasibility or changing the count. Induct on the rest." Thirty seconds, and the code that follows is now defensible.

If you cannot build the swap, say so and move: "I can't exchange the greedy item in without evicting two, so there's no exchange argument here — I'll do the O(n·W) DP instead." Announcing the failed proof is a stronger signal than a greedy solution that happens to be right, and it is the precondition check that the solving loop asks for at step 4.

The mistake that loses points: presenting a greedy rule with "this should work" or "intuitively we want the biggest one first". You have now claimed optimality without evidence, and the interviewer's next move is a counterexample you did not look for.

Check yourself

Sort the five activities by shortest duration and you also get three — the optimum. Does that make the rule correct?

No. It ends with {b, d, e} here, tying the optimum, but one passing list is not a proof. The rule loses on [0, 4), [3, 5), [4, 8): it takes the short middle interval, which blocks both neighbours, for one against two.

A colleague's rule is "take the highest-value item that still fits". What do you require before agreeing, and what do you do if it cannot be produced?

An exchange argument: swapping that item into any optimal set must not lower the total. For 0/1 knapsack it can — admitting one heavy item can evict two lighter ones — so you drop greedy and build the O(n·W) DP.

Coin denominations 1, 3 and 4, target 6. What does greedy give, what is optimal, and what does that tell you?

Greedy takes 4, then 1, then 1 — three coins. Optimal is 3 + 3, two coins. Greedy on coins is only optimal for denomination systems where the exchange goes through; on an arbitrary set it does not, so the general problem is a DP.