Greedy algorithms and exchange arguments

A greedy algorithm builds a solution one piece at a time, always taking the choice that looks best right now and never reconsidering it. Greedy algorithms are fast, simple and easy to implement, which makes them the first thing an engineer tries. Their danger is that they are often wrong: a choice that looks best locally can block a better solution later. The skill this lesson teaches is telling the two cases apart, by finding either a proof that the greedy choice is always safe or a small counterexample showing it is not.

Jonah's first real assignment is the upload window. Each NS-4 node can transmit its daily batch only while its modem holds a cellular connection, and the server's ingest process can handle one upload stream at a time on the cheap off-peak link. Each node requests a window, a start time and a finish time, during which it can upload. Dana asks how many requests can be accepted on that single link without overlaps. This is the interval scheduling problem, and it is the cleanest place to see how greedy reasoning works.

Interval scheduling

The input is a set of n intervals, each with a start time s and a finish time f. Two intervals are compatible if they do not overlap. The goal is to choose as many mutually compatible intervals as possible. Several greedy rules suggest themselves: take the interval that starts first, the shortest one, the one that conflicts with the fewest others, or the one that finishes first. Only one of them is always optimal, and small examples rule out the others quickly.

Earliest start fails when one long interval starts first and blocks many short ones. Shortest first fails when a short interval sits across the boundary of two longer compatible intervals. Fewest conflicts fails on a more elaborate example that is worth constructing once by hand. Earliest finish time works, and the intuition is that finishing early leaves the most room for everything else. Intuition is not proof, so here is the proof.

The exchange argument

Sort the intervals by finish time and let the greedy algorithm choose g₁, g₂, …, g_k, always taking the next interval that starts no earlier than the last chosen one finishes. Let o₁, o₂, …, o_m be any optimal solution, also listed in order of finish time. The claim is that greedy stays ahead: for every r ≤ k, the r-th greedy interval finishes no later than the r-th optimal interval.

The proof is by induction. For r = 1, greedy picks the interval with the earliest finish time of all, so f(g₁) ≤ f(o₁). Suppose f(g_{r−1}) ≤ f(o_{r−1}). The optimal interval o_r starts after o_{r−1} finishes, hence after g_{r−1} finishes, so o_r was available to greedy at step r. Greedy picked the available interval with the earliest finish, so f(g_r) ≤ f(o_r). Now suppose greedy chose fewer intervals than optimal, k < m. Then o_{k+1} starts after o_k finishes, which is after g_k finishes, so it was still available and greedy would not have stopped. Therefore k = m and greedy is optimal.

This style of proof, showing that greedy is never behind any optimal solution at any step, is called a stays-ahead argument. The closely related exchange argument takes an optimal solution that differs from greedy's and swaps one of its choices for greedy's choice without making it worse, repeating until the two agree. Both establish the same thing: making the greedy choice never rules out an optimal solution.

# Interval scheduling: earliest finish time first, checked against brute force
from itertools import combinations

def greedy(intervals):
    chosen, last_end = [], float('-inf')
    for s, f, name in sorted(intervals, key=lambda iv: iv[1]):
        if s >= last_end:
            chosen.append(name); last_end = f
    return chosen

def compatible(ivs):
    ivs = sorted(ivs, key=lambda iv: iv[0])
    return all(ivs[i][1] <= ivs[i + 1][0] for i in range(len(ivs) - 1))

def brute(intervals):
    for k in range(len(intervals), 0, -1):
        for sub in combinations(intervals, k):
            if compatible(sub):
                return k
    return 0

windows = [(0, 6, 'a'), (1, 3, 'b'), (2, 8, 'c'), (3, 6, 'e'),
           (4, 7, 'd'), (5, 9, 'f'), (6, 10, 'h'), (8, 11, 'g')]
g = greedy(windows)
print("greedy picks:", g, "count", len(g))
print("brute-force optimum:", brute(windows))

greedy picks: ['b', 'e', 'h'] count 3
brute-force optimum: 3

The algorithm costs O(n log n) for the sort and O(n) for the scan. Dana's 400 requests take microseconds. The brute force, which tries subsets from largest to smallest, is fine for eight intervals and hopeless for forty, but as lesson 1 recommended it makes an excellent test oracle.

Scheduling to minimize lateness

A second scheduling problem shows a different greedy rule and a cleaner exchange argument. The server must run a set of report jobs one after another on a single worker. Job j takes t_j minutes and has a deadline d_j. If a job finishes at time f_j, its lateness is max(0, f_j − d_j). The goal is to order the jobs so that the largest lateness is as small as possible. The rule that works is earliest deadline first: sort by deadline and run the jobs in that order with no idle time.

The exchange argument goes like this. An inversion in a schedule is a pair of jobs where the one with the later deadline runs first. Any schedule with an inversion has an adjacent inversion, two consecutive jobs i then j with d_i > d_j. Swapping them does not increase the maximum lateness: job j finishes earlier, so its lateness cannot grow, and job i now finishes when j used to finish, at a time f, with lateness f − d_i, which is less than j's old lateness f − d_j because d_i > d_j. Each swap removes one inversion, so after finitely many swaps any optimal schedule becomes the earliest-deadline schedule without getting worse.

Huffman coding

Greedy ideas also build data structures. Each NS-4 record includes a vehicle class code, one of eight classes from motorcycle to multi-unit truck, and a fixed 3-bit code wastes space because most vehicles are passenger cars. A prefix code assigns shorter bit strings to common symbols and longer ones to rare symbols, with no codeword a prefix of another, so the bit stream can be decoded without separators. Huffman's algorithm finds the prefix code with the smallest average length.

The algorithm keeps a priority queue of trees, initially one single-node tree per symbol weighted by its frequency. It repeatedly removes the two lightest trees, joins them under a new root whose weight is their sum, and puts the result back. After n − 1 merges one tree remains; reading 0 for each left branch and 1 for each right branch from the root to a leaf gives that symbol's codeword. With a binary heap the algorithm runs in O(n log n).

Why is merging the two rarest symbols safe? In an optimal prefix code tree, the two deepest leaves are siblings, and swapping the rarest symbols into those positions cannot increase the average length because they move deeper only by displacing symbols that are at least as frequent. So some optimal tree has the two rarest symbols as siblings, merging them reduces the problem to one with n − 1 symbols, and induction finishes the proof.

# Huffman coding for vehicle class codes (frequencies from a week of counts)
import heapq

freq = {'car': 0.62, 'light_truck': 0.18, 'heavy_truck': 0.13,
        'bus': 0.04, 'motorcycle': 0.03}

heap = [(w, i, sym) for i, (sym, w) in enumerate(sorted(freq.items()))]
heapq.heapify(heap)
counter = len(heap)
while len(heap) > 1:
    w1, _, a = heapq.heappop(heap)
    w2, _, b = heapq.heappop(heap)
    heapq.heappush(heap, (w1 + w2, counter, (a, b))); counter += 1

codes = {}
def walk(node, prefix):
    if isinstance(node, str):
        codes[node] = prefix or '0'
    else:
        walk(node[0], prefix + '0'); walk(node[1], prefix + '1')
walk(heap[0][2], '')

avg = sum(freq[s] * len(c) for s, c in codes.items())
for s in sorted(codes, key=lambda s: -freq[s]):
    print(f"{s:12s} {freq[s]:.2f}  {codes[s]}")
print(f"average bits per record: {avg:.2f} (fixed-length code: 3)")

car          0.62  1
light_truck  0.18  00
heavy_truck  0.13  011
bus          0.04  0101
motorcycle   0.03  0100
average bits per record: 1.65 (fixed-length code: 3)

The average of about 1.7 bits replaces 3 bits per record, which across 400 nodes and roughly 6,000 records per node per day saves about three million bits daily before any other compression. The real saving is larger because Maren's firmware also run-length encodes the empty intervals overnight, but Huffman's idea, that rare symbols should pay for the brevity of common ones, is the core of most compression formats, including the deflate algorithm used in compressed archives.

When greedy fails

The same habit that makes greedy attractive, never looking back, makes it wrong on many problems. Making change is the classic example. With coins of 1, 5, 10 and 25 cents, taking the largest coin that fits always uses the fewest coins. With coins of 1, 3 and 4 units, making 6 greedily gives 4 + 1 + 1, three coins, while 3 + 3 uses two. Whether greedy works depends on the coin system, and for an arbitrary system the correct method is the dynamic program of lesson 4.

A more relevant failure for Northway is the 0/1 knapsack problem. Maren has 64 KB of spare flash for optional firmware features, each with a size and a value to customers. Taking features in order of value per kilobyte is the natural greedy rule, and it can be badly wrong when a large valuable feature does not fit after smaller ones have been taken. If features could be split into fractions, the fractional knapsack, the greedy rule would be optimal; because they cannot, lesson 4 solves the problem with dynamic programming.

A recipe for greedy design

A dependable process for greedy algorithms has four steps. Cast the problem as a sequence of choices. Propose a greedy rule and immediately hunt for a small counterexample, because a counterexample found in five minutes saves a week. If none appears, prove the rule safe with a stays-ahead or exchange argument. Finally, implement with the right data structure, usually a sort or a priority queue, and test against brute force. When the counterexample hunt succeeds, the structure of the counterexample often points to the correct paradigm: if the failure comes from an early choice that should have depended on later ones, think dynamic programming.