Greedy: The Algorithm That Never Looks Back

Every algorithm we have met so far does its thinking before it commits — merge sort plans the whole split, a balanced tree fusses over every insert. This week's character does the opposite. A greedy algorithm grabs whatever looks best right now and moves on. No undo, no second thoughts. Sometimes that is provably perfect. Sometimes it is confidently, badly wrong. By Thursday you will know how to tell the two apart — and you will have watched last week's heap earn its keep inside greedy's greatest hit, Huffman coding.

Session planHow we will spend the two sessions

Section 1The algorithm that never looks back

You already run greedy algorithms all day. A cashier handing you 41 cents of change doesn't sit down and plan — they grab the biggest coin that fits, then do it again: quarter, dime, nickel, penny. At the supermarket you pick the checkout line that looks shortest right now. Packing a trunk, biggest suitcase first. Nobody computes anything. Everybody grabs.

As pseudocode, the whole family fits in four lines — and it will look like this all week, whatever the problem:

Notes 04 and 05 kept insisting that algorithms have personalities, and greedy's is easy to name: the sprinter. It is blazing fast — usually one sort and one pass, so about n log n — and it is almost embarrassingly easy to write. The question is never whether greedy is fast. It always is. The question is whether the answer it sprints to is right. Sometimes yes, provably, every time. Sometimes it is catastrophically wrong — and it will never notice, because noticing would require looking back, and looking back is the one thing it refuses to do.

Section 2Coins: a win and a face-plant

Back to the cashier. The rule is "fewest coins possible," and the greedy instinct is "always grab the biggest coin that still fits." With US coins — 25, 10, 5, 1 — making 41 cents goes: grab 25 (16 left), grab 10 (6 left), grab 5 (1 left), grab 1. Four coins, and you cannot do better. In fact, with US coins, grab-the-biggest gives the fewest coins for every amount. The instinct is not just fast here; it is perfect.

Now move to a strange little country whose coins are 1, 3 and 4, and make 6. Greedy grabs the biggest: a 4 (2 left). Nothing bigger than 1 fits anymore, so: 1, then 1 again. Three coins. But 6 = 3 + 3. Two coins — and the best answer never touches the 4 at all. Greedy's very first grab, the one that looked best, was exactly the move that ruined everything after it. And it will never know, because it never looks back.

Section 3One room, many meetings

Here is the week's headline problem, and it is as ordinary as problems get. Your company has one conference room and a pile of booking requests, each with a start time and an end time. Overlapping meetings can't share the room. Your job: approve as many meetings as possible. Not the most hours of use — the most meetings. (Two quick ground rules: back-to-back is fine — a meeting ending at 5 and one starting at 5 don't clash. And times in this section are just hours numbered 0 to 12.)

This smells greedy: go down the list, grab meetings one at a time, skip anything that clashes with what you've already approved. But "grab the best one" needs a definition of best, and that is where the fun starts. Three candidates sound reasonable. All three are wrong — and each one dies by a single small counterexample, which after §2 is exactly how you should expect a greedy idea to die.

• Shortest first? Short meetings leave more room for everyone else… right?
• Earliest start first? First come, first served — start filling the day from the morning.
• Fewest conflicts first? Genuinely clever: take the meeting that clashes with the fewest others, since it does the least damage.

The winner: earliest finish time

The rule that actually works sounds almost too dumb to be it: always take the meeting that ends soonest (among those that don't clash with what you've taken). Not the shortest, not the first to start — the first to get out of the way.

Here is why that is the right instinct. Once you approve a meeting, the only thing it leaves behind for the rest of the day is one number: when the room frees up. Everything still to come cares about that number and nothing else. So the best possible gift to your future self is the smallest one — a room that frees up as early as possible. The meeting that ends soonest leaves the most day behind.

Watch it run on a packed Tuesday — eight requests, including an all-day offsite and a web of overlaps. Sort by finishing time and sweep:

Five meetings, and no schedule can fit six into this day (that is §4's job to convince you of). Now drive it yourself — and more importantly, drive the losers. The three preset days below include the counterexamples from the figure, scaled up to real schedules.

Some things to try:

1. On A packed Tuesday, run all three strategies (or press Compare all three). Earliest start approves the Offsite first and gets 2 meetings; earliest finish gets 5.
2. On The short straddler, run shortest first. Its very first grab — the shortest meeting of the day — pokes into both workshops and caps it at 2, when 3 fit.
3. On The day-eater, earliest start gets exactly one meeting approved. All day, one meeting.
4. Now notice what never happens: earliest finish never loses. Not on these three days, not on any day you could invent. The reason is the next section.

Section 4The swap test

"It never lost in the demo" is not a reason — §2's coin greedy never loses on US amounts you happen to try either, until the day the coins change. Here is the actual reason earliest-finish is safe, in plain sentences. No formulas, and this is not a formal proof — it is "here's why you should believe it," which is the style this course uses on purpose.

Suppose a perfect scheduler — someone with infinite patience who tried every combination — hands you their plan, and it approves more meetings than greedy's. Look at the first meeting in their plan. Greedy's first pick is the earliest-ending meeting in the whole pile, so it ends no later than theirs. Swap greedy's first pick in place of theirs. Did anything break? No: the new first meeting ends at the same time or earlier, so the room frees up at the same time or sooner, so every later meeting in their plan still fits exactly as before. Same number of meetings, nothing lost.

Now do it again for the second meeting, and the third, and so on down the line. Each swap replaces one of their choices with greedy's choice and never loses a meeting. When you run out of swaps, their plan has become greedy's plan — same length as it ever was. So greedy's plan is exactly as big as the perfect plan. The perfect scheduler worked all night and tied the sprinter.

Run the test on the dead ideas from §3 and feel it fail. Shortest-first: swap the short straddler in place of a long meeting — now the plan is worse, because the straddler blocks two slots where one was blocked before. The swap "gets worse," the test jams, and sure enough a counterexample exists. The test failing doesn't just warn you — it usually points straight at the counterexample.

Section 5Huffman coding: greedy's masterpiece

In the 1830s, Samuel Morse faced a compression problem before anyone called it that: tapping out letters costs time, so which letters deserve the short taps? His answer: count how often each letter shows up in English and give the common ones the short codes — E, the most common letter, is a single dot. That instinct, done perfectly, is Huffman coding, and a version of it is working inside every zip file, JPEG and MP3 on your laptop.

Here is the setup. You want to send (or store) a message built from a small alphabet — say the letters A, B, C, D, E — using as few bits as possible. The no-thought answer is fixed width: 5 letters need 3 bits each (2 bits only give you 4 patterns), so A=000, B=001, C=010, and so on. A 20-letter message costs exactly 60 bits, no matter what it says. Fixed width ignores the one thing Morse noticed: if E appears 8 times and D appears once, E should be cheap and D can afford to be expensive.

The catch: codes you can actually decode

So give E a short code — say just 0 — and give rare letters longer ones. But now there's a trap. Suppose E = 0 and A = 00. You receive 0000. Is that EEEE? AA? EAE? The message arrives as one unbroken stream of bits — there are no spaces — so the codes themselves must make it obvious where one letter ends and the next begins.

Prefix-free codes and binary trees are the same thing wearing different clothes. Put the letters at the leaves of a binary tree; a letter's code is the path from the top down to it, writing 0 for each left turn and 1 for each right. No letter can be a prefix of another, because no leaf sits on the path to another leaf. Decoding is a walk: start at the top, follow the bits, and every time you land on a letter, write it down and jump back to the top. And the cost is staring at you: a letter's code length is just its depth in the tree. Common letters want to live near the top. Rare letters can be banished to the basement.

The greedy build: merge the two rarest

So the problem became: build a tree where the frequent letters sit high and the rare ones sit low, minimizing total bits — each letter's count times its depth, summed. David Huffman (as a grad student, dodging a final exam by solving the professor's open problem) found the greedy that does it perfectly:

Read what it is doing: the two rarest things get pushed down together, underneath a new parent — one level deeper, where rare things belong. The bundle then competes in the pool by its combined weight, so a pile of rare letters can eventually stand up to one common letter. And "repeatedly pull out the two smallest, push one back" should set off an alarm from Notes 07: that is a priority queue, and this is the moment the heap finally pays rent. Push and pop are the only moves Huffman ever makes.

Watch it run on a 20-letter message with counts A:3, B:2, C:6, D:1, E:8.

Read the codes off the final tree: E = 0, C = 10, A = 110, D = 1110, B = 1111. Prefix-free by construction. Now the bill for our 20-letter message: E pays 8×1, C pays 6×2, A pays 3×3, D pays 1×4, B pays 2×4 — that is 8 + 12 + 9 + 4 + 8 = 41 bits, against 60 bits fixed-width. A third of the message, gone, and the decoder needs no spaces, no table of lengths, nothing but the tree. This is (a piece of) how zip, PNG, JPEG and MP3 think: find what's common, make it cheap.

Some things to try:

1. Step through A lopsided message and watch the bill: each press adds exactly the new bundle's weight. Final bill: 41 against 60.
2. Switch to All letters equal. With nothing to exploit, the savings shrink — but don't vanish. (Fixed width wastes patterns: 3 bits give 8 codes and we only need 5. Huffman never wastes.)
3. One letter hogs it: predict E's code length before pressing anything. Then watch the bill — less than half of fixed width.
4. After any finished build, check the code table: no code is the start of another. That's the tree doing it, not luck.

Section 6When to reach for greedy

Greedy is the first thing you should try on any optimization problem, and the last thing you should trust. Here is the honest checklist, in the order you should run it:

And when greedy fails? That's not a dead end — it's next week. The deep reason greedy loses at {1, 3, 4} coins is that the value of grabbing the 4 depends on what you do afterwards, and greedy refuses to think about afterwards. The fix is an algorithm that grabs nothing until it has quietly worked out the answer to every smaller version of the problem first: dynamic programming — greedy that keeps receipts. It solves the coin problem, every coin set, perfectly. That's Notes 09, and Project 3 will eventually make you race the two against each other on the same problem.

To file greedy into the personality gallery from Notes 04 and 05: insertion sort is the hometown kid, brilliant on nearly-sorted days; merge sort the dependable professional, same n log n rain or shine; quicksort the gambler. Greedy is the sprinter — fastest in the field, no memory, no regrets, and either exactly right or wrong with total confidence. Your job, always, is to check which — before the race, with the swap test, because the sprinter will never check for you.

Section 7The code

Both of this week's winners are shorter than their explanations — that is the point of greedy. First, the room scheduler: one sort, one sweep, ten lines.

def best_schedule(meetings):
    """Approve as many non-overlapping meetings as possible.
    meetings: a list of (start, end) pairs. Returns the approved pairs."""
    by_finish = sorted(meetings, key=lambda m: m[1])   # earliest finish first
    approved = []
    room_free_at = None
    for start, end in by_finish:
        if room_free_at is None or start >= room_free_at:
            approved.append((start, end))     # the room is empty: take it
            room_free_at = end                # and it's busy until this ends
        # otherwise it clashes with something approved: skip, never reconsider
    return approved


tuesday = [(0, 9), (1, 3), (2, 4), (3, 5), (4, 8), (5, 7), (7, 10), (10, 12)]
print(best_schedule(tuesday))
# [(1, 3), (3, 5), (5, 7), (7, 10), (10, 12)]  — five meetings, §3's answer

And Huffman — about twenty lines, and the heap from Notes 07 does the heavy lifting. Note the arrival-counter trick in the tuples: it's the exact same tie-breaker trick from Notes 07's priority-queue section, keeping the heap from ever having to compare two trees.

import heapq

def huffman(freq):
    """freq: dict of letter -> how often it appears.
    Returns dict of letter -> its code, as a string of 0s and 1s."""
    # the pool: one entry per letter. The middle number is an arrival counter
    # so the heap never has to compare two trees (the Notes 07 tie trick).
    pool = [(f, i, {"letter": c}) for i, (c, f) in enumerate(sorted(freq.items()))]
    heapq.heapify(pool)                        # the heap finally pays rent
    next_id = len(pool)
    while len(pool) > 1:
        f1, _, a = heapq.heappop(pool)         # the rarest thing in the pool
        f2, _, b = heapq.heappop(pool)         # the second rarest
        bundle = {"left": a, "right": b}       # merge them under one parent
        heapq.heappush(pool, (f1 + f2, next_id, bundle))
        next_id += 1

    codes = {}
    def read_off(node, path):                 # walk down: left adds 0, right adds 1
        if "letter" in node:
            codes[node["letter"]] = path or "0"   # a one-letter alphabet gets "0"
        else:
            read_off(node["left"], path + "0")
            read_off(node["right"], path + "1")
    read_off(pool[0][2], "")
    return codes


freq = {"A": 3, "B": 2, "C": 6, "D": 1, "E": 8}      # 20 letters total
codes = huffman(freq)
print(codes)   # {'A': '110', 'B': '1111', 'C': '10', 'D': '1110', 'E': '0'}
bits = sum(freq[c] * len(codes[c]) for c in freq)
print(bits, "bits, vs", 3 * sum(freq.values()), "fixed-width")   # 41 vs 60

Section 8Before next session