4.25 — Greedy Algorithms & Exchange Arguments

You need to give 63p in change from coins of 1p, 5p, 10p, 20p and 50p. You take the 50p, then a 10p, then three 1p. Four coins, and it is optimal. You did not consider alternatives; you took the biggest coin that fit and repeated.

Now do it with coins of 1p, 3p and 4p, for a total of 6p. Greedy takes a 4p, then two 1p — three coins. The optimum is two 3p coins. Same algorithm, same shape of problem, and now it is wrong.

A greedy algorithm makes the choice that looks best right now and never reconsiders. When it works it is dramatically simpler and faster than dynamic programming — often O(n \log n) instead of O(n^2), with O(1) space instead of a table. When it fails it fails silently, returning a plausible answer that is not optimal. So the only interesting question about greedy algorithms is: how do you know?

1. The two properties greed needs

Greedy choice property. There is an optimal solution that includes the choice you are about to make. Not "your choice leads somewhere good" — specifically that some optimal answer contains it, so making it costs you nothing.

Optimal substructure. After making that choice, what remains is a smaller instance of the same problem, and solving it optimally gives an overall optimum. This is the same property DP needs (Chapter 4.22), which is why greedy is best understood as DP where you can prove that only one branch ever needs exploring.

The 1/3/4 coin system fails the first property. Taking the 4p leaves 2p, which needs two coins; no optimal three-coin-free solution contains that 4p. The 1/5/10/20/50 system passes it, and the reason is structural: each coin is at least twice the one below, so no combination of smaller coins can ever substitute more efficiently for a larger one. British and euro coins were designed to make greedy work; not all currencies were.

2. The exchange argument: how to actually prove it

This is the standard proof technique and the thing interviewers are really testing when they ask "why is greedy correct here".

Take any optimal solution. Show that if it differs from the greedy choice, you can swap the greedy choice in without making it worse. Therefore some optimal solution contains the greedy choice. Repeat down the line.

Worked on activity selection: given meetings with start and end times, book the most that fit in one room without overlapping.

The greedy rule: always take the meeting that ends earliest among those that still fit.

The proof. Let the optimal schedule be O and let g be the meeting that ends earliest overall. If O already contains g, done. Otherwise let f be the first meeting in O. Since g ends no later than f ends, replacing f with g in O cannot overlap anything that came after f — everything after f started after f ended, which is at or after when g ends. So the swapped schedule is still valid and has the same number of meetings, therefore it is also optimal, and it contains g. Recurse on what remains.

function maxMeetings(meetings: [number, number][]): number {
  meetings.sort((a, b) => a[1] - b[1]);           // (1)  sort by END time
  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of meetings) {
    if (start >= lastEnd) { count++; lastEnd = end; }   // (2)
  }
  return count;
}

1. The sort key is the entire algorithm. Sorting by start time is wrong (one early-starting marathon meeting blocks the day). Sorting by duration is also wrong — a short meeting in the middle can block two others. Only "ends earliest" has the exchange proof.
2. Take it if it does not overlap the last one taken.

O(n \log n), dominated by the sort. The DP alternative is O(n^2) and gives the same answer, which is exactly the payoff for having a proof.

The counterexample technique is the other half. To show greedy fails, you only need one small input where it loses. The 1/3/4 coins at 6p is one. Practise producing these quickly, because "is greedy correct here?" is usually answered fastest by trying to break it.

3. Where greedy genuinely works

Interval scheduling — most non-overlapping meetings. Sort by end time. Proven above.

Interval merging — combine overlapping ranges. Sort by start time, then extend or start a new range. Different problem, different sort key, and confusing the two is the most common interval mistake.

function merge(intervals: [number, number][]): [number, number][] {
  intervals.sort((a, b) => a[0] - b[0]);                 // (1)  by START here
  const out: [number, number][] = [];
  for (const [s, e] of intervals) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);   // (2)
    else out.push([s, e]);
  }
  return out;
}

1. Sorting by start guarantees that once you have passed an interval, nothing later can reach back before it.
2. Math.max matters: the current interval may be entirely swallowed by the previous one, and taking e blindly would shrink the merged range. This is the bug in most first attempts.

Minimum spanning tree — Kruskal and Prim, from Chapter 4.19.2. The cut property is their exchange argument.

Dijkstra — always expand the cheapest frontier vertex, from Chapter 4.19.3. Its exchange argument is why non-negative weights are required.

Huffman coding — repeatedly merge the two least frequent symbols. Chapter 1.8 built it; the exchange argument is that the two rarest symbols can always be pushed to the deepest level of an optimal tree without loss.

Fractional knapsack — take items in order of value per unit weight, splitting the last one. The fraction is what makes greed safe. 0/1 knapsack, where items cannot be split, is not greedy-solvable and needs DP, and this pair is the cleanest illustration of how small a change flips the answer.

Jump game — track the furthest index reachable so far; if it ever falls behind the current index you are stuck. O(n), one variable.

Gas station — one pass tracking a running tank; when it goes negative, the start must be after the current station. O(n), and the proof is a neat exchange argument in itself.

4. Where greedy quietly fails

Coin change with arbitrary denominations — the opening example. Needs DP.

0/1 knapsack — the classic failure. Items worth (60, weight 10), (100, 20), (120, 30) with capacity 50. Greedy by value-per-weight takes the first (ratio 6) then the second (ratio 5), reaching 160 with 20 capacity left that fits nothing. The optimum is items 2 and 3 for 220.

Longest path in a graph — always taking the longest edge available is wildly wrong. There is no polynomial algorithm at all; it is NP-hard.

Travelling salesman — "always go to the nearest unvisited city" is a reasonable heuristic that can be arbitrarily bad. Chapter 4.29 covers what to do instead.

The pattern in the failures: greedy fails when an early choice consumes a resource that a later, better choice needed. Coin change consumes value; knapsack consumes capacity. When choices are independent — scheduling, where taking a meeting only forbids overlapping ones — greed is usually safe.

5. Greedy versus DP, decided quickly

	Greedy	DP
Explores	one branch	all branches
Typical cost	O(n \log n)	O(n^2) or worse
Space	O(1)	table-sized
Correct when	the greedy-choice property holds	optimal substructure holds
Fails how	silently, with a plausible answer	it does not

The practical procedure in an interview: write the DP solution first, because it is always correct. Then ask whether a greedy rule exists, try to break it with a small counterexample, and if you cannot break it in a couple of minutes, state the exchange argument and use it. Never present a greedy solution without either a proof sketch or an explicit statement that you have tested it against the obvious traps. An interviewer who sees an unjustified greedy answer will hand you the counterexample, and it is far better to have found it yourself.

Sometimes greedy is not an optimisation but a different answer. Chapter 4.29 covers approximation: for problems where the exact answer is intractable, a greedy algorithm with a proven ratio — "never worse than twice optimal" — is the real deliverable.

What the interviewer will push on

"Why is your greedy choice correct?" They want an exchange argument, not "it seems right". State it in the standard form: take an optimal solution, show that swapping in the greedy choice keeps it valid and no worse, conclude that an optimal solution contains it.

"You sorted by end time. Why not start time or duration?" Because only end time survives the exchange argument, and the other two have one-line counterexamples: one long early meeting kills the start-time rule, and one short middle meeting kills the duration rule. Having the counterexamples ready is the tell.

"When does greedy fail?" When an early choice consumes a shared resource that a later, better choice needed. Give 0/1 knapsack with the (60,10), (100,20), (120,30) numbers, and contrast it with the fractional version where greed is optimal — one change, opposite answer.

"Can you make this greedy instead of O(n^2) DP?" Sometimes yes and you should say what would have to be true: the greedy-choice property. If you cannot prove it in a minute, say so and keep the DP. Guessing costs correctness.

"What is the complexity?" Usually the sort, so O(n \log n), with O(1) extra space. If they push on whether you can do better, the answer is generally no, because you need the ordering to make the greedy choice at all.

One thing to volunteer: mention that greedy is DP where you have proved only one branch matters. That framing explains why they share the optimal-substructure requirement, why greedy is faster, and why greedy fails in exactly the cases where the pruned branch mattered.

Recall

• Greedy needs the greedy choice property — some optimal solution contains the choice you are about to make — plus optimal substructure. It is DP with all but one branch proved unnecessary.
• Prove it with an exchange argument: take any optimal solution, swap the greedy choice in, show it is still valid and no worse.
• Disprove it with one small counterexample — coins 1/3/4 for 6p, or the 0/1 knapsack triple (60,10), (100,20), (120,30) with capacity 50.
• Interval scheduling sorts by end time; interval merging sorts by start time and extends with Math.max. Different problems, different keys.
• Greedy fails when an early choice consumes a resource a later, better choice needed — which is why fractional knapsack is greedy and 0/1 knapsack is DP.
• Greedy is typically O(n \log n) dominated by the sort, with O(1) space; DP is always correct but bigger. Greedy fails silently, so never ship it without a proof or a tested counterexample hunt.

Self-test: Give the exchange argument for sorting meetings by end time · Produce a counterexample to sorting by duration · Why is fractional knapsack greedy but 0/1 knapsack not? · What goes wrong if interval merging uses e instead of Math.max(last[1], e)? · What single structural property makes greedy coin change work for British coins?

Next: 4.26 is the problem set where the whole skill is knowing whether greed is safe — and every problem comes with the counterexample that would break the wrong rule.