The tempting shortcut
A conference centre in Kigali has one large hall and receives forty requests to use it on Saturday, each with a start and end time. The organisers want to host as many events as possible. A market trader in Oaxaca gives change and wants to hand over as few coins as possible. A file-compression program wants to give frequent letters short codes and rare letters long ones, so that the whole file shrinks as much as possible.
Each of these is an optimisation problem: among many possible solutions, find the best. And each invites the same strategy: build the solution one piece at a time, always taking the piece that looks best right now, and never reconsider. For the hall, take the event that finishes first. For change, take the largest coin that fits. For compression, merge the two rarest symbols. That strategy is called greedy.
Greedy algorithms are short, fast and easy to invent. The difficulty is that they are often wrong, and plausible-looking greedy rules fail on inputs nobody thought to try. In this lesson, two of the three strategies above are provably optimal, and one is optimal for the coins in your pocket but not for every coin system. The real subject of the lesson is the proof: how to show that a greedy choice can never lead you astray, and how to find the counterexample when it can.
Why committing early can be safe
A greedy algorithm commits to a choice before it has seen the consequences. For that to be safe, two things must be true.
- Greedy-choice property. There is some optimal solution that contains the greedy choice. We do not need every optimal solution to agree with greedy, only one.
- Optimal substructure. After making the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to it, combined with the greedy choice, is optimal for the whole.
Together they let induction do the work: the first choice is safe, the rest is a smaller problem of the same kind, so the next choice is safe too, and so on.
Two proof patterns establish the greedy-choice property again and again:
- Exchange argument. Take any optimal solution. If it differs from the greedy one, swap a piece of it for the greedy piece, and show the result is still feasible and no worse. Repeating the swap turns any optimal solution into the greedy one, so the greedy one is optimal.
- Greedy stays ahead. Measure progress step by step, and show that after every step greedy's partial solution is at least as good as the corresponding part of any other solution. If greedy is never behind, it cannot finish behind.
Analogy, not a formal construction
A hiker in fog who always steps uphill will reach a peak, but not necessarily the highest one: a small hill can trap her. Greedy algorithms work when the landscape has a single peak, or when we can prove that every uphill step stays on a path to the summit. The proofs in this lesson are proofs about the landscape.
Definitions
Definition— optimisation problem
An optimisation problem specifies a set of feasible solutions for each input and an objective to maximise or minimise. An optimal solution is a feasible solution with the best objective value; there may be several.
Definition— greedy algorithm
A greedy algorithm builds a solution by a sequence of choices, each made by a fixed local rule (the greedy rule) using only the choices made so far, and never undoes a choice.
Definition— prefix-free code
A binary code assigns each symbol a string of bits. It is prefix-free (often just called a prefix code) if no symbol's code is a prefix of another symbol's code. Then a stream of bits can be decoded left to right without separators: the first complete codeword you read is the only one possible.
Interval scheduling
Problem. Given requests, each an interval of time, choose as many as possible that are pairwise non-overlapping. (A request ending at 11:00 is compatible with one starting at 11:00.)
Several greedy rules suggest themselves, and most are wrong:
- Earliest start first fails when one very long request starts first: it blocks everything else. Requests : earliest start picks only ; the best is two.
- Shortest first fails when a short request straddles two longer compatible ones: . Shortest picks and then nothing fits; the best is .
- Fewest overlaps first sounds clever, and fails too, though the counterexample needs about a dozen intervals.
- Earliest finish first is optimal. Sort by finishing time; scan, taking every request that starts no earlier than the finish of the last one taken.
The intuition for the last rule: the request that finishes first leaves the most room for everything after it. Here is the proof.
Theorem— Earliest finish first is optimal
The earliest-finish-first algorithm selects a maximum-size set of pairwise compatible intervals, in time.
Proof
Let greedy select and let be any optimal selection, both listed in order of finishing time; we must show .
Greedy stays ahead: for every , . For , greedy chose the interval that finishes earliest of all, so . Suppose . The interval starts no earlier than , so it is compatible with and was still available when greedy made its -th choice. Greedy chose the available interval that finishes earliest, so .
Now suppose . Then starts no earlier than , so it was compatible with everything greedy chose, and greedy would not have stopped after . Contradiction; so , and greedy is optimal.
Sorting costs and the scan .
∎
import random
from itertools import combinations
def earliest_finish(requests):
chosen, free_from = [], float("-inf")
for s, f in sorted(requests, key=lambda r: r[1]):
if s >= free_from:
chosen.append((s, f))
free_from = f
return chosen
def greedy_by(rule, requests):
"""Take requests in the order given by `rule`, skipping any that overlap a chosen one."""
chosen = []
for s, f in sorted(requests, key=rule):
if all(f <= cs or s >= cf for cs, cf in chosen):
chosen.append((s, f))
return chosen
def best_by_brute_force(requests):
for size in range(len(requests), 0, -1):
for subset in combinations(sorted(requests, key=lambda r: r[1]), size):
if all(a[1] <= b[0] for a, b in zip(subset, subset[1:])):
return size
return 0
rules = {"earliest start": lambda r: r[0], "shortest": lambda r: r[1] - r[0],
"earliest finish": lambda r: r[1]}
rng = random.Random(5)
failures = {name: 0 for name in rules}
for trial in range(300):
reqs = []
for _ in range(rng.randint(3, 9)):
s = rng.randint(0, 20)
reqs.append((s, s + rng.randint(1, 8)))
best = best_by_brute_force(reqs)
assert len(earliest_finish(reqs)) == best
for name, rule in rules.items():
failures[name] += len(greedy_by(rule, reqs)) < best
print("instances (of 300) where each rule fell short of optimal:", failures)
talks = [(9, 11), (9.5, 10), (10, 12), (11, 13), (12.5, 14), (13, 15), (14, 16)]
print("hall plan:", earliest_finish(talks))A close cousin, interval partitioning, asks for the fewest halls needed to host all requests. Its greedy solution processes requests by start time and reuses the hall that frees up earliest, a natural job for a heap; you will write it in the exercises.
Fractional knapsack, and the 0/1 trap
A trader has a bag that holds kilograms and a stall of goods: saffron, cardamom, cinnamon, each with a weight available and a total value. Goods can be divided, so she may take any fraction of each. Which goods maximise the bag's value?
The greedy rule is to sort the goods by value density (value per kilogram) and fill the bag with the densest first, taking a fraction of the last item that only partly fits.
Theorem— Densest first is optimal for the fractional knapsack
Filling the bag in decreasing order of value per unit weight maximises the total value. It runs in time.
Proof
Exchange argument. Take any optimal filling. If it differs from the greedy one, then there are two items and with density such that the optimal filling takes some of while leaving some of behind. Move a small weight from to (small enough that still has left and still contains ). The weight is unchanged and the value changes by , contradicting optimality (or, if densities tie, changing nothing). So an optimal filling never leaves a denser item partly unused while using a less dense one, and the only such filling, up to ties, is the greedy one.
∎
Now forbid fractions: each item is taken whole or not at all. This 0/1 knapsack looks almost identical, but greedy by density fails. With a capacity of 10 kg and items of (6 kg, value 9), (5 kg, value 7) and (5 kg, value 7), the densest item comes first (1.5 per kg against 1.4), after which neither of the others fits: value 9. Taking the two 5 kg items gives 14. The exchange argument breaks precisely because we can no longer move a small of weight. The 0/1 knapsack needs dynamic programming, and in general it is NP-hard (Hard problems).
Coin change: when greedy works and when it fails
To pay an amount with the fewest coins, cashiers everywhere use the greedy rule: take the largest coin that does not exceed what is left, and repeat. For the euro's cent coins or the United States' , this is optimal for every amount. Coin systems with that property are called canonical.
But it is a property of the coins, not of the algorithm. With coins and amount 6, greedy pays (three coins) while needs two. History offers a real example: British coins before decimalisation in 1971 included the penny, threepence, sixpence, shilling (12 pence), florin (24 pence) and half-crown (30 pence). To pay 48 pence, greedy takes a half-crown, a shilling and a sixpence, three coins, when two florins would do.
How can we tell whether a coin system is canonical without trying every amount? Dexter Kozen and Shmuel Zaks proved in 1994 that if greedy fails at all, it already fails for some amount below the sum of the two largest coins. So a finite check suffices, and David Pearson later gave an algorithm polynomial in the number of coins. The code below computes the true optimum with a small table (the technique of the next lesson) and searches for the smallest counterexample.
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count
def optimal_coins(coins, limit):
"""fewest[a] = fewest coins summing to a, for every a up to limit (a dynamic-programming table)."""
INF = float("inf")
fewest = [0] + [INF] * limit
for a in range(1, limit + 1):
fewest[a] = min((fewest[a - c] + 1 for c in coins if c <= a), default=INF)
return fewest
def smallest_counterexample(coins):
top_two = sorted(coins)[-2:]
limit = sum(top_two) # Kozen and Zaks: a failure, if any, appears below this
fewest = optimal_coins(coins, limit)
for a in range(1, limit):
if greedy_coins(coins, a) > fewest[a]:
return a, greedy_coins(coins, a), fewest[a]
return None
systems = {
"euro cents": [1, 2, 5, 10, 20, 50],
"US cents": [1, 5, 10, 25],
"1, 3, 4": [1, 3, 4],
"pre-1971 UK pence": [1, 3, 6, 12, 24, 30],
"1, 7, 10": [1, 7, 10],
}
for name, coins in systems.items():
result = smallest_counterexample(coins)
if result is None:
print(f"{name:18} canonical: greedy is always optimal")
else:
a, g, o = result
print(f"{name:18} greedy fails first at {a}: {g} coins instead of {o}")Huffman coding
Text stored in a fixed-length code spends the same number of bits on every symbol: 8 bits per byte in ASCII, or 3 bits each if a message uses only 8 distinct letters. But letters are not equally common, and a variable-length code can give frequent symbols short codewords and rare ones long codewords. To be decodable without separators, the code should be prefix-free.
Prefix-free codes are binary trees in disguise. Put the symbols at the leaves; the path from the root spells the codeword, 0 for left and 1 for right. No codeword is a prefix of another, because no leaf lies on the path to another leaf. If symbol appears times and sits at depth , encoding the message takes
In 1951 David Huffman, a graduate student at MIT, was offered a choice by his professor Robert Fano: sit the final exam, or write a term paper on finding the most efficient such code. Fano himself, with Claude Shannon, had a method that split the symbols top-down, but it was not always optimal. Huffman found the answer by building the tree bottom-up, greedily:
- Make each symbol a one-node tree weighted by its frequency, and put all the trees in a min-heap.
- Repeatedly remove the two lightest trees, join them under a new root whose weight is their sum, and push the result back.
- When one tree remains, it is the code.
Theorem— Huffman's algorithm is optimal
Among all prefix-free binary codes for symbols with frequencies , Huffman's algorithm produces one of minimum cost. With a heap it runs in time for symbols.
Proof
Lemma 1 (greedy choice, by exchange). Let and be the two least frequent symbols. There is an optimal tree in which and are siblings at the greatest depth. Take any optimal tree; it is full (every internal node has two children, otherwise we could shorten a code), so its deepest level contains two sibling leaves and . Swap with and with . Since and , the swap changes the cost by , and likewise for and . The new tree is still optimal.
Lemma 2 (optimal substructure). Replace and by a single new symbol with . Any tree for the reduced alphabet becomes a tree for the original by giving the leaf the two children and , and , since and each sit one level below . The correction term does not depend on , so an optimal gives an optimal among trees in which and are siblings, and by Lemma 1 one of those is optimal overall.
Huffman's algorithm makes exactly this choice and then solves the reduced problem the same way, so by induction on the number of symbols it is optimal. Each of the merges is a few heap operations of .
∎
import heapq, math
from collections import Counter
from itertools import count
def huffman_code(freq):
tick = count() # tie-breaker, so trees are never compared directly
heap = [(f, next(tick), sym) for sym, f in freq.items()]
heapq.heapify(heap)
if len(heap) == 1: # one distinct symbol still needs one bit
return {heap[0][2]: "0"}
while len(heap) > 1:
f1, _, left = heapq.heappop(heap)
f2, _, right = heapq.heappop(heap)
heapq.heappush(heap, (f1 + f2, next(tick), (left, right)))
code = {}
def walk(tree, prefix):
if isinstance(tree, tuple):
walk(tree[0], prefix + "0")
walk(tree[1], prefix + "1")
else:
code[tree] = prefix
walk(heap[0][2], "")
return code
text = "a bad cab and a banana bandana"
freq = Counter(text)
code = huffman_code(freq)
for sym in sorted(code, key=lambda s: (len(code[s]), s)):
print(f"{sym!r}: {freq[sym]:2} times -> {code[sym]}")
bits = "".join(code[ch] for ch in text)
decode = {v: k for k, v in code.items()}
out, buf = [], ""
for b in bits: # prefix-free: the first complete codeword is the one
buf += b
if buf in decode:
out.append(decode[buf])
buf = ""
assert "".join(out) == text
n = len(text)
entropy = -sum(f / n * math.log2(f / n) for f in freq.values())
fixed = math.ceil(math.log2(len(freq)))
print(f"Huffman: {len(bits)} bits; fixed-length: {fixed * n} bits; 8-bit bytes: {8 * n} bits")
print(f"average {len(bits) / n:.3f} bits per symbol; entropy bound {entropy:.3f}")The last line compares the result with the entropy of the symbol frequencies. Shannon's source coding theorem says no symbol-by-symbol code can average fewer than bits per symbol, and Huffman's code is always within one bit of it. Huffman codes are inside DEFLATE (RFC 1951), and so inside every zip file, gzip stream and PNG image; JPEG uses them too. Modern compressors such as Zstandard (RFC 8878) still use Huffman codes for literal bytes but switch to arithmetic-style coders (asymmetric numeral systems) elsewhere, because a Huffman code must spend a whole number of bits per symbol and wastes up to a bit when one symbol is very common.
Common misconceptions
Misconception
"It worked on every example I tried, so the greedy rule is correct." Interval scheduling by fewest overlaps survives most small tests and is still wrong. Without an exchange or stays-ahead argument, a greedy algorithm is a heuristic. A brute-force checker on thousands of small random inputs, like the one in this lesson, is the next best thing to a proof, and the fastest way to find a counterexample.
Misconception
"Greedy coin change is optimal." Only for canonical coin systems. Most modern currencies are canonical, which is why the belief is so common; designers of new token or point systems should check, as the code above does.
Misconception
"The Huffman code for a text is unique." Ties between equal weights, and the choice of which subtree gets 0 and which gets 1, produce different codes. All of them have the same, optimal, total cost. That is why DEFLATE transmits code lengths and builds a canonical code from them.
Misconception
"A greedy algorithm that is not optimal is useless." Many greedy algorithms come with a guaranteed approximation ratio. Assigning each job to the machine that is free first finishes within twice the optimal time; repeatedly picking the set that covers the most uncovered elements solves set cover within a factor of about . When the exact problem is intractable, a provable approximation is often the best available tool (see Hard problems).
Optional Christian reflection · The largest coin first
A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.
We call these algorithms greedy because they grab whatever looks best at each moment. The coin-change counterexample is a small parable: the biggest coin first is often right and sometimes not, and only someone who looks beyond the next step can tell the difference. The book of Proverbs prizes that kind of foresight — "wisdom is better than rubies" (Proverbs 8:11, King James Version). In algorithms, the exchange argument is the wisdom that tells us when the immediate best is also the ultimate best. In life, discerning the same thing is usually harder, and worth the effort.
Exercises
1. Greedy algorithms
Warm-upHumanOne hall, many requested events, each with a start and end time. Which greedy rule always selects the largest possible number of non-overlapping events?
2. Greedy algorithms
Warm-upHumanA game's currency has coins worth 1, 7 and 10. How many coins does the greedy rule (largest coin that fits, repeatedly) use to pay 15?
3. Greedy algorithms
CoreHumanA spice trader's bag holds 10 kg. The stall offers (and any fraction may be taken):
| Spice | Weight available | Total value |
|---|---|---|
| A | 4 kg | 20 |
| B | 3 kg | 18 |
| C | 5 kg | 15 |
| D | 6 kg | 24 |
What is the maximum total value she can carry?
4. Greedy algorithms
CoreHumanA message uses five symbols with these frequencies: A appears 10 times, B 4 times, C 3 times, D 2 times and E once. Build a Huffman code. How many bits does the encoded message take in total?
5. Greedy algorithms
CoreComputationalA university must host all of a day's events, each given as (start, end) with the half-open convention (an event ending at 11 and one starting at 11 can use the same hall). Write halls_needed(events) that returns the minimum number of halls.
Use the greedy rule: process events in order of start time, and give each event a hall that has already become free if there is one, otherwise open a new hall. A min-heap of the times at which the open halls become free makes each step .
6. Greedy algorithms
StretchComputationalA print shop has one printer and a list of jobs (name, duration, deadline). Jobs run back to back starting at time 0, in an order you choose. A job finishing at time is late by . Write schedule_by_deadline(jobs) that returns (order, worst): a list of job names in the order to run them, and the maximum lateness of that schedule, which must be as small as possible.
Find the greedy rule yourself, and convince yourself with an exchange argument that it is optimal. (Hint: one of the obvious rules ignores durations entirely.)
7. Greedy algorithms
CoreHumanA pharmacist must prepare five prescriptions, one at a time, all of them requested at 9:00. Each takes a known time. To minimise the total (equivalently, the average) time customers spend waiting until their prescription is ready, in what order should she prepare them?
Further reading and resources
- A Method for the Construction of Minimum-Redundancy Codes · David A. Huffman · 1952Four pages that became part of nearly every compressed file on Earth.
- RFC 1951: DEFLATE Compressed Data Format Specification · L. Peter Deutsch · 1996The format inside zip, gzip and PNG, which combines LZ77 with Huffman codes.
- RFC 8878: Zstandard Compression and the application/zstd Media Type · 2021A modern compressor that uses Huffman codes for literals and finite-state entropy for the rest.
- Optimal bounds for the change-making problem · Dexter Kozen and Shmuel Zaks · 1994
- A polynomial-time algorithm for the change-making problem · David Pearson · 2005How to decide whether greedy change-making is optimal for a given coin system.
- Algorithms, chapter 4 (Greedy Algorithms) · Jeff Erickson
- MIT 6.046J: Design and Analysis of Algorithms · MIT OpenCourseWare