39Greedy — when the local choice wins globally

In Chapter 38 we let two pointers sweep an array, and a nested-loop search became a single honest pass. Greedy is that same instinct pushed all the way 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 startling few, that habit 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. After that we'll learn the one proof, the exchange argument, that tells the two cases 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. Say you need to make change for 6 units with the coins in front of you. You could hand a 4 then a 1 then a 1, or a 3 then another 3, or six separate 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 single leaf. That approach is correct, but it is 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 fixed rule, commits to it, and descends. The rule might be "take the biggest coin that still fits" or "take the meeting that finishes soonest". Either way it walks one path from root to leaf, with no backtracking and no comparing of alternatives. If the tree is n deep, greedy does O(n) work, while brute force does O(2ⁿ). In practice you usually pay an extra O(n log n) sort up front, to decide the order greedy 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.

Let's make that gap physical, because "exponential" gets said so often it stops meaning anything. At n = 10 the full tree has 2¹⁰ = 1024 leaves, which any laptop shrugs off. At n = 20 it has 2²⁰ = 1,048,576 leaves — a million, still fine. At n = 30 it has 2³⁰, just over a billion leaves, and your quick script now takes minutes. Every 10 extra steps multiplies the work by about 1000, because 2¹⁰ = 1024. Greedy at n = 30 makes exactly 30 committed decisions. That is the entire seduction: the tree grows like an avalanche, and greedy walks past it at a stroll. It's also why the correctness question deserves paranoia. A speedup this large is never free unless there's a proof attached — and proofs are exactly where this chapter is headed.

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, and it starts behind any shop counter. To pay 87 cents, a cashier grabs a quarter, another quarter, another quarter, a dime, and two pennies. The rule is simply the biggest coin that still fits, applied every single time. For the coins in your pocket that habit is not just fast, it is optimal — it always uses the fewest coins. So people quietly conclude that greedy "usually works". Now watch it break with one tiny change to the coin set.

Here's the tiny change: the coin set [1, 3, 4], and a bill of 6 to pay. Walk greedy's rule by hand before you read any code. The biggest coin that fits into 6 is the 4, so greedy takes it, and 6 − 4 leaves 2. The 4 no longer fits into 2, and neither does the 3. So greedy falls back to a 1, leaving 1, and then another 1, leaving 0. Three coins, done, and greedy feels great about itself. But sit with the amount 6 for a second and you'll spot what it missed: 3 + 3 pays it with two. The code below stages exactly this collision — a greedy function playing the cashier, and an optimal function acting as the referee that checks every possibility. Two functions, one amount, and a disagreement you can print.

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

Read the code line by line with me. 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, and it works from the bottom up. It builds best[amt], the fewest coins for every amount from 1 to the target, each entry reusing the smaller answers already computed. That bottom-up trick is the dynamic programming of the next chapter, but 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. That path is 4 + 1 + 1, three coins in hand. The right answer ignores the shiny 4 entirely: 3 + 3, two coins. The greedy criterion of "biggest first" walked confidently into a worse leaf, and with no backtracking it 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.

A fair question hits right here: what's so special about [1, 3, 4]? Why do the coins in your pocket behave, while this innocent-looking set lies? With US coins, the value 6 becomes 5 + 1 under greedy, and no smaller answer exists. The deep reason is that each real denomination cooperates with the ones below it — taking the biggest coin never strands you in a position the smaller coins handle badly. In [1, 3, 4] that cooperation breaks: taking the 4 from 6 leaves 2, a value only the 1s can reach. Coin systems where greedy always wins have a name, canonical systems, and here's the honest part: there is no glance test for spotting one. You either prove the greedy choice safe or you test it against a referee, exactly as we just did. Keep that discomfort. It is the chapter's whole lesson in miniature. The next chapter gives you the tool that never needs the discomfort, though it charges memory for the privilege.

from functools import cache


def make_change(coins, amount):
    """The cashier. Biggest coin that fits, again and again, no undo."""
    picked = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            picked.append(c)
    return picked, amount          # leftover != 0 -> greedy could not pay


def fewest(coins, amount):
    """The referee: the exact minimum, by dynamic programming (ch 40)."""
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]


for coins, amount in [((1, 2, 5), 8), ((1, 3, 4), 6)]:
    picked, left = make_change(coins, amount)
    best = fewest(coins, amount)
    verdict = "OPTIMAL" if len(picked) == best else "LOST by %d" % (len(picked) - best)
    print(f"{coins} -> {amount}: greedy {picked} = {len(picked)} coins, "
          f"best = {best}  [{verdict}]  leftover={left}")

losses = [a for a in range(1, 101)
          if len(make_change((1, 3, 4), a)[0]) != fewest((1, 3, 4), a)]
print(len(losses), losses[:8])

print(make_change((2, 5), 3))


# ---------- the actual run, python 3.12.7 ----------
#
# (1, 2, 5) -> 8: greedy [5, 2, 1] = 3 coins, best = 3  [OPTIMAL]  leftover=0
# (1, 3, 4) -> 6: greedy [4, 1, 1] = 3 coins, best = 2  [LOST by 1]  leftover=0
# 24 [6, 10, 14, 18, 22, 26, 30, 34]
# ([2], 1)
#
#
# ---------- reading it ----------
#
# 1. The two runs share EVERY line of make_change. Nothing about the code
#    knows which coin system it is holding. Only the data changed.
#
# 2. 24 of the first 100 amounts lose, and look at the losers: 6, 10, 14,
#    18, 22, ... every fourth number from 6. Not bad luck, not an edge case
#    -- an arithmetic progression. Greedy is SYSTEMATICALLY wrong on this
#    system. Any amount of the form 4k + 2 puts a 4 in greedy's hand and
#    strands a 2 that only 1s can pay.
#
# 3. The leftover is the honest part of the return value. With coins
#    (2, 5) and amount 3, greedy takes one 2 and then cannot move: 1 is
#    unpayable and there is no 1-coin to fall back on. It returns
#    ([2], 1) -- "here is what I took, and I still owe you 1."
#    A function that returned just [2] would be claiming it paid 3 with 2.
#    Greedy's failure mode is not an exception; it is a confident wrong
#    answer, so the ONLY protection is a return value that can express
#    "I did not finish."
#
# 4. Why (1, 2, 5) is safe and (1, 3, 4) is not: in (1, 2, 5) every coin
#    can absorb the smaller-coin pile it replaces without ever losing --
#    two 1s become a 2, a 2 + two 1s become... and so on. That property has
#    a name, CANONICAL, and it is the exchange argument of section 03 doing
#    the work. In (1, 3, 4) the optimal answer for 6 is {3, 3}, and no
#    subset of {3, 3} sums to 4 -- the 4 can never be exchanged in, so
#    "biggest first" is simply the wrong rule for that 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; 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.

Before the code, feel why this is a real decision and not a triviality. Plausible rules crowd around you: take the earliest-starting talk, so the room never sits idle? One marathon talk starting at 9am kills the whole day, so that rule dies fast. Or take the shortest talk, so that each one blocks the least amount of time? That sounds efficient too, and we'll break it with real numbers in a moment. Every rule sounds reasonable in the mouth of the person proposing it, and that's exactly why the field demands a proof. Notice the stakes as the input grows. With 8 talks there are 2⁸ = 256 possible subsets, so a brute-force referee can still check them all. With 40 talks there are 2⁴⁰ subsets, about a trillion, and the referee quietly drops out of the race. A one-pass rule that's provably right isn't just faster — it's the difference between answering and not answering.

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 the talks by finish time, then walks the list exactly once. It keeps a talk only if that talk starts at or after the last kept talk ended. I ran it against a brute-force referee that checks all 2⁸ possible talk subsets, and the biggest compatible set really is 3, and greedy finds it. Why does finishing-earliest win? Because it frees the room as early as possible, and that can never hurt. The more time left in the day, the more room there is for whatever comes next.

That intuition becomes a proof through the exchange argument, the master key for every greedy correctness claim. Take any optimal schedule, and compare its first talk with greedy's first talk. Greedy's finishes no later, because finishing earliest is exactly how greedy chose it. So swap the optimal schedule's first talk for greedy's. The new first talk frees the room at least as early, so nothing later overlaps it. The schedule is still valid and still the same size, which means it is still optimal. Repeat that swap down the line, one position at a time. You have morphed some optimal solution into greedy's 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.

Run the exchange once with real numbers to see there's no trick hiding in it. Suppose some optimal schedule opens with a talk running 2–5, and greedy opened with A, which runs 1–4. Greedy's pick finishes at 4, the optimal's at 5, so greedy's finishes first — that's guaranteed, it's the sort order. Now perform the swap: pull out the 2–5 talk and drop A in its place. Every later talk in that optimal schedule started at 5 or after, and A is done by 4, so nothing collides. The count didn't change either — we removed one talk and added one. The schedule is still legal, still the same size, and therefore still optimal, just with greedy's choice at the front. That's the whole machine of the proof. Each swap costs nothing, and after enough swaps the optimal schedule is greedy's schedule.

So why does the rule say earliest-finishing, and not, say, the shortest talk? 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), and Z(6–10), three talks on one timeline. "Shortest first" grabs Y, which overlaps both of its neighbours, so it blocks X and Z and ends with just 1 talk. Earliest-finish grabs X then Z — 2 talks, and I ran both rules to confirm the numbers are exactly that. The criterion, then, isn't decoration but the whole proof of correctness.

you type
$ python greedy_idiom.py

# ---------- 1. sort-then-take: interval scheduling, earliest FINISH first ----------
from operator import itemgetter

talks = [("intro", 9, 10), ("deep dive", 9, 12), ("panel", 10, 11),
         ("demo", 11, 13), ("wrap", 12, 13)]
chosen, free_at = [], 0
for name, start, end in sorted(talks, key=itemgetter(2)):
    if start >= free_at:                 # the ONLY test
        chosen.append(name)
        free_at = end                    # commit
print(chosen)
print(len(chosen), free_at)

# ---------- 2. same shape, budget is money, criterion is computed ----------
parts = [("ssd", 120, 90), ("ram", 80, 60), ("gpu", 400, 250), ("psu", 90, 70)]
budget, cart = 300, []
for name, price, value in sorted(parts, key=lambda p: p[2] / p[1], reverse=True):
    if price <= budget:
        cart.append(name)
        budget -= price
print(cart, budget)

# ---------- 3. only want the best k? do not sort all of it ----------
import heapq
freq = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
print(heapq.nlargest(3, freq, key=freq.get))
print(heapq.nsmallest(2, freq.items(), key=itemgetter(1)))
print(max(freq, key=freq.get))

# ---------- 4. the trap ----------
xs = [5, 2, 9]
print(xs.sort())
print(xs)

# ---------- 5. reverse=True is not [::-1] ----------
ties = [("b", 1), ("a", 1), ("c", 0)]
print(sorted(ties, key=itemgetter(1), reverse=True))
print(sorted(ties, key=itemgetter(1))[::-1])

you see
['intro', 'panel', 'demo']
3 13
['psu', 'ssd', 'ram'] 10
['a', 'd', 'b']
[('f', 5), ('e', 9)]
a
None
[2, 5, 9]
[('b', 1), ('a', 1), ('c', 0)]
[('a', 1), ('b', 1), ('c', 0)]

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, and the lazy scheme gives every character the same width. In ASCII that width is 8 bits, 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. Morse code plays the same trick, giving e a single dot. In 1952 a student named David Huffman found the provably shortest such code. The algorithm is pure greed: repeatedly merge the two rarest symbols into one combined node, until a single tree remains.

Let's give the algorithm something real to chew on. Take a 100-character text using six symbols, with these counts: a appears 45 times, b 13, c 12, d 16, e 9, and f just 5. Check the total: 45 + 13 + 12 + 16 + 9 + 5 = 100. A fixed-width code needs 3 bits per symbol, since 2 bits give only 4 patterns and we have 6 symbols. So the fixed cost is 100 × 3 = 300 bits, full stop, no matter which letters dominate. But look at that skew — a alone is nearly half the text. Every bit we shave off a's code gets saved 45 times over, while a longer code for f only costs us 5 small payments. That trade is the entire idea, and the greedy merge below is just the machine that finds the best possible version of it.

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. We keep it in a min-heap, a structure from earlier, so "the two rarest" is always just two heappops. Each round fuses those two into one node whose weight is the sum, and pushes it back into the heap. Every symbol on the left branch gets a 0 prepended to its code, and every symbol on the right gets a 1. 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, and the classic frequencies compress to 224 bits versus 300 for a fixed 3-bit code. The most common letter, a, 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 lives at 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 one. This prefix-free property is the quiet genius of building codes from a tree. The stream is unambiguous with no separators at all. And that's not a lucky side effect of greed — it's guaranteed, because greedy only ever puts symbols at leaves.

And why is "merge the two rarest" the provably right greed? The exchange argument comes straight back. In any best tree, the two deepest slots — the longest codes — must belong to the two rarest symbols. Suppose they didn't, and common a (weight 45) sat at depth 4 while rare f (weight 5) sat at depth 1. Those two positions contribute 45 × 4 + 5 × 1 = 185 bits to the total. Swap the two letters and the same slots cost 5 × 4 + 45 × 1 = 65 bits, a saving of 120 with nothing else touched. So any tree that puts a common symbol deep can be traded up, which means the best tree never does. Huffman's merge just builds that fact in from the start: the rarest pair gets fused first, so they end up deepest. Greedy here isn't a gamble — it's the exchange argument running in fast-forward.

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.

Put a price tag on the difference, because it's the honest cost of correctness. For the amount 6 with coins [1, 3, 4], greedy made 3 quick subtractions and stopped. The referee filled six slots, best[1] through best[6], and tried all 3 coins in each — roughly 18 small checks. You can verify a few slots yourself: best[3] is 1 and best[5] is 2, a 4 plus a 1. And best[6] is 2 — the 3 + 3 that greedy missed. Eighteen versus three barely registers at this scale. But raise the target to 100,000 and DP does about 300,000 checks, while greedy still makes only a handful of subtractions. That's the real trade on the table. Greedy is the cheap answer you must prove, and dynamic programming is the guaranteed answer you must pay for.

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

Out in the wild, you'll rarely be told "this is a greedy problem". You'll be handed a goal instead: schedule the most jobs, wire the network for the least cable, route the packet the cheapest way. Then you alone must decide whether the greedy shortcut is a proof or a trap. Here is the drill, and it's the same every time. It has two prongs, and you'll learn to run both of them at the same time.

Name the greedy rule out loud, like "take the earliest-finishing" or "merge the two rarest". Then run two attacks on it in parallel. Prove it: can you show the greedy choice is always swappable into some optimal solution, using the exchange argument? If yes, you're done, because 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". And if it does break, 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 already 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. Think of the 3 you skipped, the talk you passed up, the move that quietly 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 it's 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. →