16 — Greedy algorithms

A greedy algorithm builds a solution one piece at a time, and at each step takes the choice that looks best right now, without reconsidering it later. No backtracking, no table of subproblems: one pass, usually after a sort. When a greedy algorithm is correct it is typically the fastest and shortest solution available, often $O(n \log n)$ for the sort and $O(n)$ after it.

The difficulty is that “looks best right now” can be defined in several plausible ways, and most of them are wrong. For choosing the most non-overlapping meetings, “earliest finishing first” is optimal, while “shortest first” and “earliest starting first” are not, and the counterexamples are three intervals long. So the core skill with greedy algorithms is not writing them, which usually takes a few lines, but knowing whether a particular greedy rule is correct: proving it, or finding the counterexample that disproves it. This chapter treats both as first-class.

Every implementation was checked against a brute-force or dynamic-programming reference on hundreds of random inputs. Timings were measured with Python 3.14 on one Mac using time.perf_counter; exact numbers will differ elsewhere.

Prim’s and Kruskal’s minimum spanning tree algorithms and Dijkstra’s shortest paths are greedy algorithms too; they are covered with their proofs in chapter 13. Huffman coding’s heap mechanics are in chapter 9; here the focus is on why it is optimal.

What makes a greedy algorithm correct

Two properties together make a greedy algorithm optimal:

• Greedy-choice property. There is an optimal solution that contains the greedy first choice. Making that choice never rules out reaching an optimum.
• 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.

Optimal substructure is shared with dynamic programming (chapter 14). The difference is the greedy-choice property: dynamic programming considers every possible first choice and takes the best of their subproblem answers; a greedy algorithm commits to one first choice without looking at the subproblems at all. That is why greedy algorithms are faster when they work, and why they need a proof that the committed choice is safe.

Two proof techniques cover almost every greedy algorithm in practice. Both are shown on the same problem.

Activity selection

Problem. Given $n$ activities with start and finish times $[s_i, f_i)$, select the largest number of activities that do not overlap. (Half-open intervals: an activity that ends at 5 is compatible with one that starts at 5.)

Greedy rule. Sort by finish time. Take the first activity; then repeatedly take the next activity whose start is at or after the finish of the last one taken.

def select_activities(intervals):
    """Max number of pairwise non-overlapping half-open intervals [s, f)."""
    chosen, last_end = [], float("-inf")
    for s, f in sorted(intervals, key=lambda iv: iv[1]):   # earliest finish first
        if s >= last_end:
            chosen.append((s, f))
            last_end = f
    return chosen

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_activities(meetings))

[(1, 4), (5, 7), (8, 11), (12, 16)]

Walking through the sorted order (by finish time): (1, 4) finishes first and is taken. (3, 5) and (0, 6) start before 4 and are skipped. (5, 7) starts at 5, after 4, and is taken. (3, 9), (5, 9) and (6, 10) start before 7. (8, 11) is taken. (8, 12) and (2, 14) overlap it. (12, 16) is taken. Four activities, which the brute-force check confirms is the maximum.

Complexity. $O(n \log n)$ for the sort, $O(n)$ for the scan, $O(n)$ space for the sorted copy.

Proof 1: the exchange argument

An exchange argument takes an arbitrary optimal solution and transforms it, one swap at a time, into the greedy solution, without ever making it worse.

Let $g_1$ be the activity with the earliest finish time, and let $O$ be any optimal solution, with its activities sorted by finish time as $o_1, o_2, \ldots, o_k$. If $o_1 = g_1$, the greedy choice is already in an optimal solution. Otherwise, replace $o_1$ by $g_1$ to get $O'$. Because $g_1$ finishes no later than any activity, $f(g_1) \le f(o_1) \le s(o_2)$, so $g_1$ does not overlap $o_2$ or anything after it. $O'$ is valid and has the same size $k$, so it is also optimal and contains $g_1$. That is the greedy-choice property.

For optimal substructure: once $g_1$ is chosen, the remaining problem is to pick the most activities among those starting at or after $f(g_1)$, which is the same problem on a smaller input. Applying the argument again to that subproblem, and inductively all the way down, shows the greedy solution has the same size as an optimal one.

The general pattern: “Suppose an optimal solution differs from the greedy one. Find the first place they differ. Swap the optimal solution’s choice for the greedy one. Show the result is still feasible and no worse.” It works whenever the greedy choice can be substituted into any solution.

Proof 2: greedy stays ahead

A staying-ahead argument shows that after each step, the greedy partial solution is at least as good as any other solution’s partial solution by some measure, so the greedy solution cannot finish behind.

Let the greedy activities, in order, be $g_1, \ldots, g_m$ and an optimal solution’s be $o_1, \ldots, o_k$, both sorted by finish time. Claim: for every $r \le m$, $f(g_r) \le f(o_r)$. The greedy solution’s $r$-th activity finishes no later than the optimal solution’s $r$-th.

By induction. For $r = 1$ it holds because $g_1$ has the earliest finish of all activities. Suppose it holds for $r - 1$. Then $f(g_{r-1}) \le f(o_{r-1}) \le s(o_r)$, so $o_r$ was still available when the greedy algorithm chose $g_r$. The greedy algorithm picks the earliest-finishing available activity, so $f(g_r) \le f(o_r)$.

Now suppose $k > m$. By the claim, $f(g_m) \le f(o_m) \le s(o_{m+1})$, so $o_{m+1}$ was compatible with everything greedy had chosen, and greedy would not have stopped at $m$. Contradiction; so $m = k$.

Staying-ahead proofs suit algorithms that build a sequence where “progress so far” has a natural measure (finish time here, reach in Jump Game, coverage in interval covering). Exchange arguments suit algorithms where the solution is a set and elements can be substituted (Huffman coding, job sequencing, minimum spanning trees).

The wrong greedy rules

Three other rules for activity selection sound reasonable:

The section on testing greedy ideas, at the end of the chapter, shows a harness finding counterexamples for the first two automatically, and failing to find one for the third by random search, which is a lesson in itself.

Interval scheduling variants

Activity selection is one of a family of interval problems. Sorting by finish time is right for maximizing the count; other objectives need other orders.

Minimum arrows is activity selection in disguise: a set of pairwise non-overlapping balloons needs one arrow each, and the greedy shot at each chosen finish bursts everything overlapping it. The only change is that balloons are closed intervals, so touching endpoints count as overlapping (the comparison becomes s > last_end). Mixing up open and closed endpoints is a frequent bug in this family.

Weighted interval scheduling, where each interval has a value and the goal is maximum total value, is not solvable greedily: one heavy interval can be worth more than many light ones. It is a DP over intervals sorted by finish time with binary search for the last compatible interval, $O(n \log n)$ (chapter 14).

Minimum meeting rooms and platforms

Problem. Given meetings $[s_i, f_i)$, find the fewest rooms so that no two overlapping meetings share a room. The railway version asks for the fewest platforms given arrival and departure times.

The key fact. The answer equals the maximum number of meetings in progress at any single moment. That many rooms are clearly necessary. They are also sufficient: process meetings by start time and give each one any room that is free; a new room is opened only when every existing room is busy, which means the number of rooms in use never exceeds the current overlap.

Two implementations. The heap version assigns rooms explicitly: a min-heap holds the end time of each room’s current meeting, and a new meeting reuses the room whose meeting ends earliest if it has ended.

import heapq


def min_rooms(intervals):
    """Rooms needed so that no two overlapping [s, f) meetings share one."""
    ends = []                                    # min-heap of end times in use
    for s, f in sorted(intervals):
        if ends and ends[0] <= s:
            heapq.heapreplace(ends, f)          # reuse the room freed earliest
        else:
            heapq.heappush(ends, f)
    return len(ends)

The sweep version computes the maximum overlap directly from the sorted start and end times, treating each as an event:

def min_rooms_sweep(intervals):
    starts = sorted(s for s, _ in intervals)
    ends = sorted(f for _, f in intervals)
    rooms = best = j = 0
    for s in starts:
        while j < len(ends) and ends[j] <= s:    # departures before or at this arrival
            rooms -= 1
            j += 1
        rooms += 1
        best = max(best, rooms)
    return best

print(min_rooms([(0, 30), (5, 10), (15, 20)]))
print(min_rooms_sweep([(900, 910), (940, 1200), (950, 1120), (1100, 1130), (1500, 1900), (1800, 2000)]))

2
3

In the platform example, the trains at 9:40, 9:50 and 11:00 are all in the station at 11:00, so three platforms are needed.

Complexity. Both are $O(n \log n)$ time and $O(n)$ space. The sweep is usually faster in practice (two sorts, no heap); the heap version is needed when the actual room assignment is wanted.

The tie rule. ends[j] <= s means a meeting ending at 10 frees its room for a meeting starting at 10. If the problem says the end time is inclusive (a train departing at 10:00 still occupies the platform at 10:00, so a train arriving at 10:00 needs another platform), the comparison must be <. Both versions above use the half-open convention; the brute-force check counts, at every start time, how many intervals contain it under the same convention.

Fractional knapsack, and why 0/1 is different

Problem. Items have values $v_i$ and weights $w_i$; a bag holds weight $W$. In the fractional version, any fraction of an item may be taken, with proportional value. Maximize total value.

Greedy rule. Sort by value density $v_i / w_i$, highest first. Take whole items while they fit, then the fraction of the next item that fills the bag.

def fractional_knapsack(items, cap):
    total = 0.0
    for v, w in sorted(items, key=lambda it: it[0] / it[1], reverse=True):
        if cap == 0:
            break
        take = min(w, cap)
        total += v * take / w
        cap -= take
    return total

Proof (exchange). Suppose an optimal solution uses less of the densest item $a$ than is available, while there is room taken up by some less dense item $b$. Move a small weight $\epsilon$ from $b$ to $a$: the total weight is unchanged and the value changes by $\epsilon (v_a/w_a - v_b/w_b) \ge 0$. Repeating this, an optimal solution can be transformed to take as much of the densest item as possible, then of the next densest, which is exactly the greedy solution. Time $O(n \log n)$; with a linear-time weighted median, $O(n)$ is possible but rarely worth it.

The 0/1 counterexample. If items must be taken whole, the same density rule fails:

items = [(60, 10), (100, 20), (120, 30)]     # (value, weight); densities 6, 5, 4
print(fractional_knapsack(items, 50), greedy_01(items, 50), knap01(items, 50))

240.0 160 220

greedy_01 takes items by density while they fit: the 60 and the 100, leaving 20 units of room that the 120 item (weight 30) cannot use. The optimum, from the DP, is 100 + 120 = 220. The exchange argument breaks because it relied on moving an arbitrarily small $\epsilon$ of weight between items; with indivisible items the only moves are whole items, and swapping a whole item can leave capacity unused. The 0/1 problem is NP-hard in general; the $O(nW)$ DP is in chapter 14, and the fractional greedy reappears there as the bounding function for branch and bound in chapter 15.

Jump Game I and II

Jump Game I. Each nums[i] is the maximum jump length from index $i$. Starting at index 0, can the last index be reached?

The greedy state is a single number: the farthest index reachable so far. Scan left to right; if the current index is beyond that reach, it is unreachable and so is everything after it. Otherwise extend the reach with i + nums[i].

def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + x)
    return True

Correctness is a staying-ahead invariant: after processing index $i$, reach is the maximum index reachable using only jumps from indices $0..i$, and every index up to reach is reachable (if you can reach index $j$ you can reach every index between 0 and $j$, since a jump can be shorter than its maximum). $O(n)$ time, $O(1)$ space.

Jump Game II. The last index is guaranteed reachable; find the minimum number of jumps.

This is BFS on the implicit graph where index $i$ has edges to $i+1..i+\text{nums}[i]$, but the BFS levels are contiguous ranges of indices, so no queue is needed. Level $k$ is the range of indices reachable in exactly $k$ jumps and not fewer. Scanning the current level computes the farthest index the next level reaches; when the scan hits the end of the current level, one more jump is spent and the next level begins.

def min_jumps(nums):
    """Fewest jumps from index 0 to the last index (assumed reachable)."""
    jumps, end, far = 0, 0, 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:              # current window exhausted: must jump
            jumps += 1
            end = far
    return jumps

print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]), min_jumps([2, 3, 1, 1, 4]))

True False 2

For [2, 3, 1, 1, 4]: level 0 is index 0; from it the farthest reach is 2, so level 1 is indices 1 to 2; from those, the farthest reach is $1 + 3 = 4$, the last index. Two jumps. In [3, 2, 1, 0, 4], every path lands on the 0 at index 3 and the reach never passes 3.

The loop stops at len(nums) - 2: once the last index is inside the current level there is no need to jump again. Running the loop through the last index adds a spurious jump when end lands exactly on it. The implementation was checked against an explicit BFS on random arrays, including zeros. $O(n)$ time, $O(1)$ space. The DP alternative (dp[j] = min(dp[i] + 1) over all $i$ that reach $j$) is $O(n^2)$.

Gas Station

Problem. $n$ stations on a circular route; station $i$ provides gas[i] and driving from $i$ to $i + 1$ costs cost[i]. Starting with an empty tank, from which station can the car complete the circuit? Return −1 if none.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:            # cannot reach i + 1 from start, nor from any station in between
            start, tank = i + 1, 0
    return start

print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
print(can_complete_circuit([2, 3, 4], [3, 4, 3]))

3
-1

Why the one-pass method is correct

Write $d_i = \text{gas}[i] - \text{cost}[i]$ for the net change in fuel from station $i$ to $i + 1$. Two facts carry the proof.

Fact 1: skipping is safe. Suppose starting at $a$, the tank first goes negative on the way from $b$ to $b + 1$; that is, $d_a + \cdots + d_b < 0$ while every shorter prefix $d_a + \cdots + d_j$ (for $a \le j < b$) is $\ge 0$. Consider starting instead at any $k$ with $a < k \le b$. Then

$d_k + \cdots + d_b = (d_a + \cdots + d_b) - (d_a + \cdots + d_{k-1}) < 0 - 0$

because the first sum is negative and the subtracted prefix is non-negative. So starting at $k$ also runs dry by $b + 1$. Arriving at $k$ with a non-negative tank can only help, so a start between $a$ and $b$ is no better than $a$ was. Every station from $a$ to $b$ can be ruled out at once, and the search restarts at $b + 1$. This is why the scan is $O(n)$ rather than $O(n^2)$.

Fact 2: if the total is non-negative, the last candidate works. Let $s$ be the start the scan ends with. The scan proved the tank stays non-negative from $s$ to the end of the array, ending with surplus $P = d_s + \cdots + d_{n-1} \ge 0$. The prefix before it, $d_0 + \cdots + d_{s-1}$, consists of segments that each ended in a failure, so it is negative; call it $-Q$ with $Q > 0$. The total is $P - Q \ge 0$, so $P \ge Q$. When the car wraps around from $s$ and drives $0, 1, \ldots, s-1$, every prefix of that stretch is at least $-Q$ (each failing segment’s own prefixes were non-negative until its final step), so the tank never drops below $P - Q \ge 0$.

The check sum(gas) < sum(cost) covers the remaining case: if the total is negative, no start works, since a full lap ends with a negative tank from any start. If the total is non-negative, a valid start always exists and the scan finds one. When several starts are valid (possible only when some prefix sums are exactly zero), this method returns one of them, not necessarily the smallest index; the test checked that its answer is a valid start, and that it returns −1 exactly when brute force finds no start. Time $O(n)$, space $O(1)$.

Job sequencing with deadlines

Problem. $n$ jobs each take one unit of time and have a profit and a deadline; job $i$ earns its profit only if it finishes by time $d_i$. One job runs at a time. Maximize total profit.

Greedy rule. Consider jobs from highest profit to lowest. Schedule each in the latest free time slot at or before its deadline; if there is none, drop it.

def job_sequencing(jobs):
    """jobs: (profit, deadline); unit time each; returns max total profit."""
    max_d = max((d for _, d in jobs), default=0)
    slot = [None] * (max_d + 1)                  # slot[t] holds the job run in (t-1, t]
    total = 0
    for p, d in sorted(jobs, reverse=True):      # highest profit first
        for t in range(min(d, max_d), 0, -1):    # latest free slot not after the deadline
            if slot[t] is None:
                slot[t] = p
                total += p
                break
    return total

print(job_sequencing([(100, 2), (19, 1), (27, 2), (25, 1), (15, 3)]))

142

100 takes slot 2, 27 takes slot 1 (slot 2 is full), 25 and 19 find slot 1 taken and are dropped, 15 takes slot 3: 142.

Why the latest slot. Placing a job as late as possible leaves earlier slots free for jobs with tighter deadlines, and any job that could use a later slot can also use an earlier one only if its deadline allows; the latest-slot choice never blocks something another choice would have allowed.

Why highest profit first (exchange). A set of jobs is feasible if it can be scheduled, which holds exactly when, for every $t$, at most $t$ of the jobs have deadline $\le t$ (schedule by earliest deadline to check). Feasible sets have the matroid exchange property: if $A$ and $B$ are feasible and $\lvert A \rvert < \lvert B \rvert$, some job of $B$ can be added to $A$ keeping it feasible. For any matroid, considering elements in decreasing weight and keeping each one that preserves feasibility gives a maximum-weight independent set (Rado and Edmonds’ theorem). Kruskal’s algorithm is the same theorem applied to the graphic matroid of a graph’s forests. This is the cleanest general answer to “when does sort-by-value greedy work”: when the feasible sets form a matroid.

Complexity and the faster version. The slot scan costs up to $O(d)$ per job, so $O(n \cdot d_{\max})$ worst case, which is quadratic when deadlines are large. A disjoint-set union where each slot points to the latest free slot at or before it makes each lookup near-constant (chapter 12 covers union-find):

def job_sequencing_dsu(jobs):
    max_d = max((d for _, d in jobs), default=0)
    parent = list(range(max_d + 1))              # parent[t]: latest free slot <= t
    def find(t):
        while parent[t] != t:
            parent[t] = parent[parent[t]]
            t = parent[t]
        return t
    total = 0
    for p, d in sorted(jobs, reverse=True):
        t = find(d)
        if t > 0:
            total += p
            parent[t] = t - 1
    return total

Slot 0 is a sentinel meaning “no free slot”. Measured with every deadline equal to $n$, the worst case for the scan, since each new job walks past every slot already filled:

The scan grows by about 100× per 10× more jobs, the quadratic signature. An alternative is to sort by deadline and keep a min-heap of chosen profits, evicting the smallest whenever the heap’s size exceeds the current deadline; that is also $O(n \log n)$. A relative of it solves Course Schedule III, where jobs have different durations and the goal is the most jobs: sort by deadline, keep a max-heap of durations, and evict the longest job whenever the total time passes the current deadline.

Huffman coding and why it is optimal

Problem. Given symbol frequencies, find a prefix-free binary code (no codeword is a prefix of another) minimizing the total encoded length $\sum_i f_i \cdot \text{len}(c_i)$.

Algorithm. Repeatedly remove the two lowest-frequency nodes from a min-heap, merge them under a new parent whose frequency is their sum, and push the parent back. The final tree’s root-to-leaf paths are the codewords. The tree-building and code extraction are covered in chapter 9; the total encoded length is simply the sum of the merge costs, since each merge adds one bit to every symbol beneath it:

def huffman_cost(freqs):
    """Total encoded length in bits = sum of all merge costs."""
    if len(freqs) <= 1:
        return 0 if not freqs else freqs[0]  # convention: one symbol uses 1 bit
    h = list(freqs)
    heapq.heapify(h)
    cost = 0
    while len(h) > 1:
        a = heapq.heappop(h); b = heapq.heappop(h)
        cost += a + b
        heapq.heappush(h, a + b)
    return cost

For frequencies 45, 13, 12, 16, 9 and 5 (the standard textbook example), Huffman’s cost is 224 bits, against 300 for a fixed 3-bit code. The test compared huffman_cost with an exhaustive search over every possible sequence of pairwise merges (every full binary tree arises from some merge sequence) on random frequency lists, and they agreed every time.

The optimality proof

Represent a prefix code as a full binary tree (every internal node has two children; a node with one child could be removed, shortening codewords). Two lemmas, both exchange arguments, carry the proof.

Lemma 1 (greedy choice). There is an optimal tree in which the two least frequent symbols $x$ and $y$ are siblings at the maximum depth.

Take any optimal tree. Its deepest level has at least two leaves that are siblings, say $a$ and $b$ (in a full binary tree, a deepest leaf’s sibling is also a leaf). Swap $x$ with $a$. Since $f_x \le f_a$ and $\text{depth}(a) \ge \text{depth}(x)$, the cost changes by

$(f_a - f_x)\,(\text{depth}(x) - \text{depth}(a)) \le 0$

so the tree is still optimal. Swap $y$ with $b$ the same way.

Lemma 2 (optimal substructure). Replace $x$ and $y$ by a single symbol $z$ with $f_z = f_x + f_y$. If $T'$ is optimal for the reduced alphabet, then expanding $z$ into a parent of $x$ and $y$ gives an optimal tree $T$ for the original alphabet.

Expanding $z$ adds exactly $f_x + f_y$ to the cost, so $\text{cost}(T) = \text{cost}(T') + f_x + f_y$. If some tree $U$ for the original alphabet were cheaper than $T$, by Lemma 1 it can be taken to have $x$ and $y$ as siblings; collapsing them gives a tree for the reduced alphabet costing $\text{cost}(U) - f_x - f_y < \text{cost}(T')$, contradicting the optimality of $T'$.

Huffman’s algorithm is exactly “merge the two smallest, then solve the reduced problem”, so by induction on the alphabet size it is optimal. Optimality here means among symbol-by-symbol prefix codes with integer codeword lengths. Arithmetic coding and asymmetric numeral systems can beat Huffman on skewed distributions because they are not restricted to whole bits per symbol; Huffman’s cost is within one bit per symbol of the entropy bound. Ties between equal frequencies can produce different trees with different codeword lengths, all with the same optimal total cost.

Complexity. $n - 1$ merges with heap operations: $O(n \log n)$. If the frequencies are already sorted, a two-queue method (one queue of leaves, one of merged nodes, which are created in non-decreasing order) runs in $O(n)$.

Minimum coins: canonical systems

Problem. Given coin denominations (with a 1 so every amount is reachable), pay an amount with the fewest coins.

Greedy rule. Repeatedly take the largest coin that does not exceed the remaining amount.

def greedy_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else None

For US coins $\{1, 5, 10, 25\}$ this is optimal; the test compared it with the DP for every amount below 500. For $\{1, 3, 4\}$ and amount 6:

print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))

3 2

Greedy pays $4 + 1 + 1$; the optimum is $3 + 3$. Taking the 4 is the locally best move, and it leaves a remainder of 2 that only 1s can pay. The greedy-choice property fails: no optimal solution for 6 contains a 4.

A coin system for which greedy is optimal for every amount is called canonical. Most real currencies are canonical, but it is a property of the specific denominations and cannot be assumed. Some facts:

• If a system is not canonical, the smallest amount where greedy fails is less than the sum of the two largest coins (Kozen and Zaks, 1994). So canonicity can be checked by comparing greedy with the DP for every amount up to that sum, in $O(k \cdot (c_{k-1} + c_k))$ time for $k$ coins. A polynomial $O(k^3)$ test also exists (Pearson, 2005).
• Adding a coin to a canonical system can break canonicity. $\{1, 5, 10, 25\}$ is canonical, but $\{1, 5, 10, 20, 25\}$ is not: greedy pays 40 as $25 + 10 + 5$ (three coins) instead of $20 + 20$.

Running the check over a few systems, reporting (smallest failing amount, greedy count, optimal count):

[1, 5, 10, 25] None
[1, 2, 5, 10, 20, 50, 100, 200] None
[1, 3, 4] (6, 3, 2)
[1, 7, 10] (14, 5, 2)
[1, 10, 25] (30, 6, 3)
[1, 5, 10, 20, 25] (40, 3, 2)

The general problem, for arbitrary denominations, is the unbounded knapsack DP (Coin Change) in chapter 14, $O(k \cdot \text{amount})$:

def dp_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] < INF else None

Container With Most Water

Problem. Given heights $h_0, \ldots, h_{n-1}$ of vertical lines at positions $0..n-1$, choose two lines that, with the x-axis, hold the most water: maximize $(j - i) \cdot \min(h_i, h_j)$.

Algorithm. Start with the widest pair $i = 0$, $j = n - 1$. Record its area, then move inward whichever pointer is at the shorter line. Stop when the pointers meet.

def max_area(h):
    i, j, best = 0, len(h) - 1, 0
    while i < j:
        best = max(best, (j - i) * min(h[i], h[j]))
        if h[i] < h[j]:
            i += 1          # h[i] can never do better with any j' < j
        else:
            j -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))

49

The best pair is positions 1 and 8, heights 8 and 7: width 7, height 7.

Why moving the shorter side is safe

Suppose $h_i < h_j$. Every pair that uses line $i$ with some other line $j' < j$ (all the pairs not yet examined that include $i$) has

$\text{area}(i, j') = (j' - i) \cdot \min(h_i, h_{j'}) \le (j' - i) \cdot h_i < (j - i) \cdot h_i = \text{area}(i, j)$

The width is strictly smaller and the height is capped by $h_i$ no matter how tall $h_{j'}$ is. So every remaining pair involving $i$ is worse than the pair just recorded, and discarding line $i$ loses nothing. Moving the taller side instead would discard pairs that might be better. When $h_i = h_j$, the same argument applies to both lines, so moving either is safe.

Each step discards one line, so the loop runs $n - 1$ times: $O(n)$ time, $O(1)$ space. Measured against the $O(n^2)$ check of all pairs on random heights:

This is a greedy argument (each step makes an irrevocable decision to discard a line) wearing the clothes of the two-pointer pattern from chapter 4. The proof style, “the discarded element cannot be part of any better answer”, is the same one that justifies two-pointer pair sum on sorted arrays.

Interval covering

Problem. Given closed intervals and a target range $[lo, hi]$, choose the fewest intervals whose union covers it, or report that it cannot be covered. (Variants: Video Stitching, Minimum Number of Taps to Open to Water a Garden.)

Greedy rule. Keep covered, the right end of the covered prefix (initially $lo$). Among all intervals that start at or before covered, pick the one that reaches farthest right; it becomes the next interval. Repeat until covered $\ge hi$. If no interval extends beyond covered, there is a gap.

def min_cover(intervals, lo, hi):
    """Fewest closed intervals whose union covers [lo, hi]; None if impossible."""
    ivs = sorted(intervals)
    count, covered, i = 0, lo, 0
    while True:
        best = None
        while i < len(ivs) and ivs[i][0] <= covered:     # every interval starting in reach
            if best is None or ivs[i][1] > best:
                best = ivs[i][1]
            i += 1
        if best is None or best < covered:
            return None
        count += 1
        covered = best
        if covered >= hi:
            return count

print(min_cover([(0, 3), (2, 6), (3, 4), (6, 10), (5, 8), (1, 5)], 0, 10))

3

From 0, only (0, 3) starts in reach; covered becomes 3. Intervals starting at or before 3 are (1, 5), (2, 6) and (3, 4); the farthest reach is 6. From 6, (5, 8) and (6, 10) start in reach; 10 wins. Three intervals.

Proof (staying ahead). After $k$ greedy picks, the covered prefix reaches at least as far as the covered prefix of any $k$ intervals that cover $[lo, hi]$ without gaps. Each optimal interval’s start must be within the previously covered prefix (or there would be a gap), so it was among greedy’s candidates, and greedy picked the candidate with the farthest end. So greedy reaches $hi$ in no more picks than the optimum.

Sorting is $O(n \log n)$; the scan is $O(n)$ in total because i only moves forward. The random comparison with brute force covers the edge cases that matter: point intervals (a, a), a gap that makes the target unreachable, and no interval starting at or before $lo$. On integer positions where intervals only need to touch at integer points (“cover every integer”), the rule changes to ivs[i][0] <= covered + 1, which is a different problem; read the specification.

Jump Game II is this same algorithm in disguise: index $i$ is the interval $[i, i + \text{nums}[i]]$.

Assign Cookies and greedy matching

Problem. Child $i$ is content with a cookie of size at least $g_i$; there are cookies of sizes $s_j$, each given to at most one child. Maximize the number of content children.

Greedy rule. Sort both lists. Give each cookie, smallest first, to the least greedy child it satisfies; equivalently, walk both sorted lists with two pointers.

def find_content_children(greed, sizes):
    greed, sizes = sorted(greed), sorted(sizes)
    child = 0
    for s in sizes:                       # smallest cookie first
        if child < len(greed) and s >= greed[child]:
            child += 1                    # least greedy unsatisfied child gets it
    return child

print(find_content_children([1, 2, 3], [1, 1]), find_content_children([1, 2], [1, 2, 3]))

1 2

Proof (exchange). Let child $c$ be the least greedy child and cookie $k$ the smallest cookie that satisfies $c$. In any optimal assignment, if $c$ gets a larger cookie $k'$ and $k$ goes to some child $c'$ (who therefore has $g_{c'} \le s_k \le s_{k'}$), swapping gives $c$ the cookie $k$ and $c'$ the cookie $k'$, and both stay content. If $c$ is unsatisfied in the optimum, giving $k$ to $c$ (taking it from whoever had it) does not reduce the count. Either way some optimal solution matches $c$ with $k$, and the rest is the same problem on the remaining children and cookies. Cookies too small for $c$ are too small for every child and can be discarded, which is what the loop does when the condition fails.

$O(n \log n + m \log m)$ time. The same “sort both sides, match the smallest sufficient partner” structure solves Boats to Save People (sort, pair the heaviest with the lightest if they fit), task-to-worker assignment where each worker can do tasks up to a skill level, and bipartite matching problems whose compatibility is a threshold on one number. When compatibility is an arbitrary relation, greedy matching fails and a real bipartite matching algorithm is needed.

Testing a greedy idea against brute force

Proofs are the reliable way to know a greedy algorithm is correct, but in practice the first question is cheaper: is there a small counterexample? A greedy rule that is wrong is usually wrong on an input of three to six elements, and an exhaustive or DP solver for inputs that small takes a few lines. Comparing the two on thousands of random small inputs finds most wrong greedy rules in seconds.

import random


def find_counterexample(greedy, exact, generate, trials=10_000, seed=0):
    """Return the smallest input (by generate's size) where greedy != exact."""
    rng = random.Random(seed)
    best = None
    for t in range(trials):
        case = generate(rng)
        if greedy(case) != exact(case):
            if best is None or len(case) < len(best[0]):
                best = (case, greedy(case), exact(case), t)
    return best


def random_intervals(rng):
    out = []
    for _ in range(rng.randint(1, 6)):
        s = rng.randint(0, 12)
        out.append((s, s + rng.randint(1, 6)))
    return out


def by_rule(key):
    def pick(intervals):
        chosen = []
        for iv in sorted(intervals, key=key):
            if all(iv[1] <= c[0] or c[1] <= iv[0] for c in chosen):
                chosen.append(iv)
        return len(chosen)
    return pick

by_rule(key) builds an activity-selection greedy for any ordering, and max_compatible_brute (not shown) tries every subset from largest to smallest. Three rules, 10,000 random cases each:

rules = {
    "earliest finish": lambda iv: iv[1],
    "earliest start": lambda iv: iv[0],
    "shortest first": lambda iv: iv[1] - iv[0],
}
for name, key in rules.items():
    r = find_counterexample(by_rule(key), max_compatible_brute, random_intervals)
    if r is None:
        print(f"{name:16} no counterexample in 10,000 random cases")
    else:
        case, g, e, t = r
        print(f"{name:16} {case}  greedy={g} optimal={e}  (trial {t})")

earliest finish  no counterexample in 10,000 random cases
earliest start   [(7, 13), (10, 11), (7, 9)]  greedy=1 optimal=2  (trial 116)
shortest first   [(9, 13), (5, 9), (8, 11)]  greedy=1 optimal=2  (trial 234)

Both wrong rules were refuted with three-interval inputs, and the counterexamples are readable:

earliest start (sort is stable, so (7, 13) is tried before (7, 9)):
  7 ---------------- 13          taken first; blocks everything else
  7 ---- 9                       optimal: (7, 9) and (10, 11)
           10 - 11

shortest first:
           8 ---- 11             shortest (length 3), taken first
  5 ------ 9                     overlaps it
           9 ------- 13          overlaps it
                                 optimal: (5, 9) and (9, 13)

The first counterexample also exposes a tie-breaking dependence: with the equal starts in the other order, earliest-start would have taken (7, 9) and been right on this input. Randomized testing exercises tie orders that a hand-made example usually does not.

What the harness does not prove. “Earliest finish: no counterexample” is evidence, not proof; the proofs earlier in the chapter are what establish it. The limits show up with the fourth rule, “fewest conflicts first”. The harness, run for 20,000 random cases of up to six intervals, found nothing. Yet the rule is wrong; its counterexamples are structured, like this 11-interval layout (fewest_conflicts repeatedly takes the remaining interval that overlaps the fewest others, then discards everything it overlaps):

classic = [(0, 2), (1, 3), (1, 3), (1, 3), (2, 4), (3, 5), (4, 6), (5, 7), (5, 7), (5, 7), (6, 8)]
print("fewest conflicts on 11-interval case:", fewest_conflicts(classic), "optimal:", max_compatible_brute(classic))

fewest conflicts on 11-interval case: 3 optimal: 4

The middle interval (3, 5) has the fewest conflicts (two), so the rule takes it first, but the optimum is the four intervals (0, 2), (2, 4), (4, 6), (6, 8), none of which is (3, 5). Random inputs of six intervals cannot contain this structure, and random inputs of eleven rarely produce it. Practical consequences:

• Generate inputs small enough that brute force is instant, but vary the size, and include adversarial shapes (many ties, nested intervals, stacked duplicates) alongside uniform random ones.
• When the harness finds a counterexample, the minimal one is usually the most informative; keep the smallest seen, as find_counterexample does, or shrink it by deleting elements while it still fails.
• When it finds nothing, look for a proof. If neither a proof nor a counterexample appears, prefer the DP.

When greedy fails, and what to use instead

The last row shows another role for greedy algorithms: when the exact problem is NP-hard, a greedy algorithm with a proven approximation ratio is often the practical answer. Greedy set cover is within a factor of about $\ln n$ of optimal, and that is essentially the best possible in polynomial time unless P = NP.

Summary