39Greedy — when the local choice wins globally

In Chapter 38 we let two pointers sweep an array and turned a nested-loop search into a single honest pass. Greedy takes that same instinct to the edge: at every step, take the choice that looks best right now and never take it back. It sounds reckless — one path down the tree, no second-guessing — and for most problems it is. But for a surprising few it lands the globally best answer for almost no work. Here's the plan. We'll watch greedy nail the optimum, then watch it fail on a coin set you'll break with your own hands, then learn the one proof — the exchange argument — that tells the two apart. The whole way through we keep asking the single question that decides everything: can a chain of locally-best moves add up to the globally-best answer? By the end you'll look at a brand-new problem and say, before writing a line, whether the fast never-look-back move is a proof or a trap.

01The greedy move: commit now, never look back

Let's start with what every optimization problem really is underneath: a tree of choices. To make change for 6 units you could hand over a 4, then a 1, then a 1; or a 3 then a 3; or six 1s. Each sequence of picks is a path down a branching tree, and the leaves are the finished answers. Brute force (chapter 35) walks the whole tree and compares every leaf. It's correct, but explosive: a tree with a two-way choice at each of n steps has 2ⁿ leaves. Now watch what greedy does instead.

Greedy refuses to branch. At every node it applies one rule — "take the biggest coin that still fits", "take the meeting that finishes soonest" — commits to it, and descends. One path, root to leaf. No backtracking, no comparing alternatives. If the tree is n deep, greedy does O(n) work where brute force does O(2ⁿ). (Usually there's also an O(n log n) sort up front, to decide the order it considers things in.) The entire gamble is this: can a sequence of locally-best moves add up to the globally-best answer? When it can, you get an exponential speedup for free.

So what decides whether "best now" equals "best overall"? Let's find a problem where it's obviously true, and one where it's disastrously false. Start with the disaster. →

02When greedy lies: the coin that costs you

Making change is the folk-tale example of greedy. To pay 87 cents, a cashier grabs a quarter, another quarter, another quarter, a dime, two pennies — the biggest coin that fits, every time. For the coins in your pocket that habit isn't just fast, it's optimal: it always uses the fewest coins. So people conclude greedy "usually works". Watch it break with a tiny change to the coin set.

def greedy(coins, target):
    n = 0
    for c in sorted(coins, reverse=True):   # biggest coin first
        while target >= c:                  # grab it while it fits
            target -= c
            n += 1
    return n

def optimal(coins, target):                 # dynamic programming — chapter 40
    best = [0] + [float("inf")] * target
    for amt in range(1, target + 1):        # smallest sub-amount up
        for c in coins:
            if c <= amt:
                best[amt] = min(best[amt], best[amt - c] + 1)
    return best[target]

print(greedy([1, 3, 4], 6))   # 3   ->  4 + 1 + 1
print(optimal([1, 3, 4], 6))  # 2   ->  3 + 3

Line by line: greedy sorts the coins large-to-small, then for each denomination subtracts it as many times as it fits, counting coins. optimal is the honest answer. It builds up best[amt] — the fewest coins for every amount from 1 to the target — with each one reusing the smaller answers already computed. That's the dynamic programming of the next chapter; here it's just the referee. The last two lines are the verdict, and I ran them: greedy prints 3, optimal prints 2.

Greedy grabbed the 4 because it was biggest, then had to patch the leftover 2 with two 1s: 4 + 1 + 1, three coins. The right answer ignores the shiny 4 entirely: 3 + 3, two coins. The greedy criterion — "biggest first" — walked confidently into a worse leaf and, with no backtracking, never noticed. Across the first 100 targets with the set [1, 3, 4], greedy is beaten on 24 of them (6, 10, 14, 18, 22, …). It isn't occasionally unlucky; it is systematically wrong for this coin system.

If greedy is a claim, we need to test the claim. When it's true, there's a beautiful reason — and it comes with its own famous winning problem. →

03The exchange argument: proving greedy right

Here is the problem greedy was born for. You have one lecture hall and a pile of talks, each with a start and finish time, and overlapping talks can't share the room. Which talks do you accept to fit the most into the day? The winning rule is almost insultingly simple: always take the talk that finishes earliest among those that still fit. Not the shortest, not the earliest-starting — the earliest-finishing.

def schedule(acts):                       # acts: (name, start, finish)
    chosen, last_finish = [], -1
    for name, s, f in sorted(acts, key=lambda a: a[2]):   # by finish time
        if s >= last_finish:              # doesn't overlap what we took
            chosen.append(name); last_finish = f
    return chosen

acts = [("A",1,4),("B",3,5),("C",0,6),("D",5,7),
        ("E",3,9),("F",5,9),("G",6,10),("H",8,11)]
print(schedule(acts))     # ['A', 'D', 'H'] — 3 talks

The loop sorts by finish time, then walks once, keeping a talk only if it starts at or after the last kept talk ended. I ran it against a brute-force check of every one of the 2⁸ possible talk subsets: the biggest compatible set really is 3, and greedy finds it. Why does finishing-earliest win? Because it leaves the room free as early as possible, and that can never hurt — the more time left, the more room for what's next.

That intuition becomes a proof through the exchange argument, the master key for every greedy correctness claim. Take any optimal schedule. Look at its first talk versus greedy's first talk. Greedy's finishes no later — that's how greedy chose it. So swap the optimal's first talk for greedy's. The new first talk frees the room at least as early, nothing else overlaps, and the schedule is still valid and still the same size — still optimal. Repeat down the line, and you've morphed some optimal solution into greedy's, one step at a time, without ever losing a talk. So greedy's answer is optimal too. No choice greedy makes can be "traded up" to a better one — because the best solution can always be traded down to greedy's.

Why earliest-finishing and not, say, shortest? Because a different rule fails the exchange test, and you can catch it with a three-talk counterexample. Take X(1–5), Y(4–7), Z(6–10). "Shortest first" grabs Y and blocks both X and Z, ending with 1 talk. Earliest-finish grabs X then Z — 2 talks. I ran both, and the numbers are exactly that. The criterion isn't decoration; it's the whole proof.

One earliest-finish rule, one exchange proof, an exponential speedup. Now meet the greedy algorithm running silently inside almost every file on your disk. →

04Huffman: the greedy algorithm in every file you own

Text is stored as bits. The lazy scheme gives every character the same width — 8 bits in ASCII — whether it's a hyper-common e or a rare q. That's wasteful. Frequent symbols should get short codes, and rare ones can afford long codes, the way Morse code gives e a single dot. In 1952 a student named David Huffman found the provably shortest such code, and the algorithm is pure greed: repeatedly merge the two rarest symbols into one combined node, until a single tree remains.

import heapq

def huffman(freq):
    forest = [[w, i, {s}] for i, (s, w) in enumerate(freq.items())]
    heapq.heapify(forest)                    # a min-heap by weight
    code, nxt = {s: "" for s in freq}, len(freq)
    while len(forest) > 1:
        w1, _, s1 = heapq.heappop(forest)    # the rarest bundle
        w2, _, s2 = heapq.heappop(forest)    # the next rarest
        for s in s1: code[s] = "0" + code[s] # prepend a bit to each side
        for s in s2: code[s] = "1" + code[s]
        heapq.heappush(forest, [w1+w2, nxt, s1|s2]); nxt += 1
    return code

freq = {"a":45, "b":13, "c":12, "d":16, "e":9, "f":5}
code = huffman(freq)
bits = sum(freq[s] * len(code[s]) for s in freq)
print(bits, "vs", 3 * sum(freq.values()))   # 224 vs 300

The forest starts as one tiny tree per symbol, kept in a min-heap (a structure from earlier) so "the two rarest" is always two heappops. Each round fuses them: every symbol on the left branch gets a 0 prepended to its code, every symbol on the right a 1, and the merged node — its weight the sum of the two — goes back in the heap. After n−1 merges one tree is left, and each symbol's code is its path of 0s and 1s from the root. I ran it: the classic frequencies compress to 224 bits versus 300 for a fixed 3-bit code. a, the most common, got the 1-bit code 0, while rare f got 1100. That's a 25% saving, and it is provably the smallest any code can achieve for these frequencies.

Because every symbol is a leaf, no code can be the start of another one. The instant the bits trace a path down to a leaf, that's the letter, and decoding jumps back to the root for the next. This prefix-free property is the quiet genius of building codes from a tree: the stream is unambiguous with no separators at all. That's not a lucky side effect of greed. It's guaranteed, because greedy only ever puts symbols at leaves.

The knob below is why compression works at all. Skew the frequencies and watch the savings appear; flatten them and watch the savings vanish. It runs the real Huffman merge, live.

Greedy commits to one choice and proves it never needed the others. Its rival keeps all the choices alive. Time to put them face to face. →

05Greedy vs dynamic programming: commit vs consider

The coin change split the world in two. Greedy took the biggest coin and moved on. The optimal function did something different: it computed the best answer for every smaller amount and combined them. It never committed early; it kept every sub-answer and reused them. That's dynamic programming (the next chapter), and the contrast is the cleanest way to understand both.

Two techniques, one decision. So how do you know, on a brand-new problem, which one you're holding — before you've bet the system on it? →

06How to know before you trust it

You'll rarely be told "this is a greedy problem". You'll be handed a goal — schedule the most jobs, wire the network for the least cable, route the packet the cheapest way — and you have to decide whether the greedy shortcut is a proof or a trap. Here is the drill. It's the same every time.

Name the greedy rule ("take the earliest-finishing", "merge the two rarest"). Then run two attacks in parallel. Prove it: can you show the greedy choice is always swappable into some optimal solution — the exchange argument? If yes, you're done — greedy is optimal and fast. Break it: at the same time, throw small inputs at it and compare against a brute-force referee, exactly as we did with the coins. A single counterexample kills greedy forever. You don't get to say "but it works most of the time". If it breaks, you already know the escape hatch: dynamic programming.

This chapter's real gift is a way of thinking, and it's bigger than algorithms. You use greedy reasoning every day: paying with the biggest bills, running errands nearest-first, packing the fullest boxes. It's a superb heuristic — a fast, good-enough rule of thumb. The 1% move is to hold two thoughts at once: reach for the simple local rule first, and in the same breath ask what it's ignoring. Greedy fails exactly when a locally-worse choice now buys a better position later — the 3 you skipped, the talk you passed up, the move that sets up the next three. Naming that failure mode is a life skill. It's why you sometimes take the smaller reward now to keep the bigger one open, and why "obviously best right now" always deserves one hard look before you commit.

But the coin change that greedy botched still needs its right answer — and so do knapsacks, edit distance, and the longest path through a lattice of choices. The fix is to stop re-solving what you have already solved. The next chapter turns "remember your subproblems" into the most powerful technique in this whole volume: dynamic programming. →