Skip to content
LumenaryAcademy
Algorithms 60 min

Greedy algorithms

Take the step that looks best right now and never look back — when that is optimal, how to prove it, and how to spot when it is not.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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.

IntuitionH

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.

  1. 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.
  2. 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.

DefinitionsH

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.

ExplanationH

Interval scheduling

Problem. Given nn requests, each an interval [si,fi)[s_i, f_i) 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 [0,10),[1,2),[3,4)[0, 10), [1, 2), [3, 4): earliest start picks only [0,10)[0, 10); the best is two.
  • Shortest first fails when a short request straddles two longer compatible ones: [0,5),[4,6),[5,10)[0, 5), [4, 6), [5, 10). Shortest picks [4,6)[4, 6) and then nothing fits; the best is [0,5),[5,10)[0, 5), [5, 10).
  • 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 O(nlog⁡n)O(n \log n) time.

Proof

Let greedy select g1,g2,…,gkg_1, g_2, \ldots, g_k and let o1,o2,…,omo_1, o_2, \ldots, o_m be any optimal selection, both listed in order of finishing time; we must show k≥mk \ge m.

Greedy stays ahead: for every i≤min⁡(k,m)i \le \min(k, m), f(gi)≤f(oi)f(g_i) \le f(o_i). For i=1i = 1, greedy chose the interval that finishes earliest of all, so f(g1)≤f(o1)f(g_1) \le f(o_1). Suppose f(gi)≤f(oi)f(g_i) \le f(o_i). The interval oi+1o_{i+1} starts no earlier than f(oi)≥f(gi)f(o_i) \ge f(g_i), so it is compatible with g1,…,gig_1, \ldots, g_i and was still available when greedy made its (i+1)(i+1)-th choice. Greedy chose the available interval that finishes earliest, so f(gi+1)≤f(oi+1)f(g_{i+1}) \le f(o_{i+1}).

Now suppose m>km > k. Then ok+1o_{k+1} starts no earlier than f(ok)≥f(gk)f(o_k) \ge f(g_k), so it was compatible with everything greedy chose, and greedy would not have stopped after gkg_k. Contradiction; so k≥mk \ge m, and greedy is optimal.

Sorting costs O(nlog⁡n)O(n \log n) and the scan O(n)O(n).

∎

python
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))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

ExplanationH

Fractional knapsack, and the 0/1 trap

A trader has a bag that holds WW 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 O(nlog⁡n)O(n \log n) time.

Proof

Exchange argument. Take any optimal filling. If it differs from the greedy one, then there are two items ii and jj with density di>djd_i > d_j such that the optimal filling takes some of jj while leaving some of ii behind. Move a small weight ε\varepsilon from jj to ii (small enough that ii still has ε\varepsilon left and jj still contains ε\varepsilon). The weight is unchanged and the value changes by ε(di−dj)>0\varepsilon(d_i - d_j) > 0, 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 ε\varepsilon of weight. The 0/1 knapsack needs dynamic programming, and in general it is NP-hard (Hard problems).

ExplanationH

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 1,2,5,10,20,501, 2, 5, 10, 20, 50 or the United States' 1,5,10,251, 5, 10, 25, 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 1,3,41, 3, 4 and amount 6, greedy pays 4+1+14 + 1 + 1 (three coins) while 3+33 + 3 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.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

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 cc appears f(c)f(c) times and sits at depth d(c)d(c), encoding the message takes

cost(T)=∑cf(c) d(c) bits.\text{cost}(T) = \sum_{c} f(c)\, d(c) \text{ bits.}

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:

  1. Make each symbol a one-node tree weighted by its frequency, and put all the trees in a min-heap.
  2. Repeatedly remove the two lightest trees, join them under a new root whose weight is their sum, and push the result back.
  3. When one tree remains, it is the code.

Theorem— Huffman's algorithm is optimal

Among all prefix-free binary codes for symbols with frequencies ff, Huffman's algorithm produces one of minimum cost. With a heap it runs in O(nlog⁡n)O(n \log n) time for nn symbols.

Proof

Lemma 1 (greedy choice, by exchange). Let xx and yy be the two least frequent symbols. There is an optimal tree in which xx and yy 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 aa and bb. Swap xx with aa and yy with bb. Since f(x)≤f(a)f(x) \le f(a) and d(x)≤d(a)d(x) \le d(a), the swap changes the cost by (f(a)−f(x))(d(x)−d(a))≤0(f(a) - f(x))(d(x) - d(a)) \le 0, and likewise for yy and bb. The new tree is still optimal.

Lemma 2 (optimal substructure). Replace xx and yy by a single new symbol zz with f(z)=f(x)+f(y)f(z) = f(x) + f(y). Any tree T′T' for the reduced alphabet becomes a tree TT for the original by giving the leaf zz the two children xx and yy, and cost(T)=cost(T′)+f(x)+f(y)\text{cost}(T) = \text{cost}(T') + f(x) + f(y), since xx and yy each sit one level below zz. The correction term does not depend on T′T', so an optimal T′T' gives an optimal TT among trees in which xx and yy 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 n−1n - 1 merges is a few heap operations of O(log⁡n)O(\log n).

∎

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The last line compares the result with the entropy H=−∑cpclog⁡2pcH = -\sum_c p_c \log_2 p_c of the symbol frequencies. Shannon's source coding theorem says no symbol-by-symbol code can average fewer than HH 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 misconceptionsH

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 ln⁡n\ln n. 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

Exercises

1. Greedy algorithms

Warm-upHuman

One hall, many requested events, each with a start and end time. Which greedy rule always selects the largest possible number of non-overlapping events?

Choose one

2. Greedy algorithms

Warm-upHuman

A 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

CoreHuman

A 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

CoreHuman

A 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

CoreComputational

A 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 O(log⁡n)O(\log n).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Greedy algorithms

StretchComputational

A 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 tt is late by max⁡(0,t−deadline)\max(0, t - \text{deadline}). 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.)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Greedy algorithms

CoreHuman

A 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?

Choose one

Further reading and resources