Greedy: Proving a Local Choice Is Globally Right

Every greedy algorithm has the same shape: sort by some key, walk the list, take whatever is still feasible. That part is three lines. It is never the difficult part, and it is never where the mistakes are.

The difficulty is entirely in two questions. Which key? and why does taking the best-looking option now never cost you later? Get the first wrong and the code still runs, returning answers that are plausible and sometimes even optimal on the cases you tried. Skip the second and you do not have an algorithm, you have a heuristic that you have not measured.

So greedy is best understood as a proof technique with a small amount of code attached. This lesson is about the proofs: two general-purpose argument shapes, and one theorem that settles the question exactly.

One resource, a set of requests each with a start and an end time, and the goal of accepting as many non-overlapping requests as possible. Four sorting keys suggest themselves, and intuition picks a losing one.

• Earliest start. Requests $[0,100]$, $[1,2]$, $[3,4]$. Greedy takes the long one and accepts 1; the optimum is 2.
• Shortest duration. Requests $[0,10]$, $[9,11]$, $[10,20]$. The shortest is $[9,11]$, which blocks both others. Greedy accepts 1; the optimum is 2.
• Fewest conflicts. Plausible, and it also fails, though the counterexample needs a larger construction.
• Earliest finish time. This one is optimal.

The intuition behind the winner: finishing early is the only property that leaves the largest possible remainder of the timeline for everything still to come. Duration and start time both fail because neither controls when the resource is handed back.

def schedule(requests):
    """requests: list of (start, end). Returns a maximum compatible subset."""
    chosen, last_end = [], float("-inf")
    for start, end in sorted(requests, key=lambda r: r[1]):   # by finish time
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

The running time is $O(n \log n)$, dominated by the sort; the scan itself is linear. Compare that against solving the same problem by dynamic programming, which would need a table over request indices and a search for the last compatible request.

Nothing in this code hints that it is correct. Change r[1] to r[0] and you get the earliest-start version, which is wrong, and the diff is one character. The correctness lives in an argument that is nowhere in the file.

The exchange argument never tries to prove greedy is optimal directly. It starts from an arbitrary optimal solution and transforms it into the greedy one, one swap at a time, showing that no swap ever makes it worse.

Step C is where the sort key earns its keep. Because greedy always takes the earliest available finish time, its choice frees the resource at least as early as whatever the optimal solution chose, so everything the optimal solution scheduled afterwards still fits.

The pattern generalises far beyond scheduling. Whenever you want to justify a greedy rule, the first thing to try is: assume an optimum that disagrees with me, and show I can force it to agree without penalty.

The second standard proof shape, named this way in Kleinberg and Tardos's Algorithm Design, proves an invariant instead of performing swaps.

Let greedy's accepted requests be $g_1, g_2, \ldots$ and any optimal solution's be $o_1, o_2, \ldots$, both in order of finish time. Claim: for every $r$, greedy's $r$-th request finishes no later than the optimum's $r$-th.

It holds for $r = 1$ because greedy takes the globally earliest finish. If it holds at $r-1$, then $o_r$ begins after $o_{r-1}$ ends, which is at or after when $g_{r-1}$ ends, so $o_r$ was available when greedy made its $r$-th pick. Greedy takes the earliest finisher among available requests, so $g_r$ finishes no later.

Now suppose the optimum has more requests than greedy. Then $o_{k+1}$ was still available when greedy stopped, and greedy would have taken it.

Huffman's 1952 paper in the Proceedings of the IRE builds a minimum-redundancy prefix code, and its greedy choice is not a sorting key. It is a merge: repeatedly combine the two lowest-frequency symbols into one node whose frequency is their sum.

With frequencies $a{:}45$, $b{:}13$, $c{:}12$, $d{:}16$, $e{:}9$, $f{:}5$ out of 100, the merges run $e+f = 14$, then $c+b = 25$, then $14+d = 30$, then $25+30 = 55$, then $45+55$. The resulting code costs 224 bits per 100 symbols against 300 for a 3-bit fixed-length code.

The exchange argument again: in some optimal tree the two rarest symbols are siblings at maximum depth. If they are not, swap them there. Moving rarer symbols deeper and commoner ones shallower cannot increase the total, so an optimal tree with that shape exists, which is exactly what the merge assumes.

Ad hoc proofs invite the question of whether there is a general criterion. There is. A matroid is a ground set $E$ with a family $\mathcal{I}$ of subsets called independent, satisfying:

1. The empty set is independent.
2. Hereditary: any subset of an independent set is independent.
3. Exchange: if $A$ and $B$ are independent and $|A| < |B|$, some element of $B$ can be added to $A$ keeping it independent.

The Rado-Edmonds theorem, from Edmonds's 1971 paper Matroids and the greedy algorithm in Mathematical Programming, says: for a hereditary system, the greedy algorithm finds a maximum-weight independent set for every linear weight function precisely when the system is a matroid. The condition is not merely sufficient, it is necessary.

Kruskal's 1956 minimum spanning tree algorithm is exactly this. Sets of edges containing no cycle form the graphic matroid, so sorting edges by weight and adding whatever keeps the set acyclic is optimal by the theorem, with no bespoke proof required.

Outside a matroid, greedy loses its exactness guarantee, and what remains depends on the structure.

Sometimes you get an approximation instead. Maximising a monotone submodular function under a cardinality constraint is not a matroid problem, and greedy is not optimal, but it is provably within a factor of $1 - 1/e$ of the best possible. The submodular-optimization path develops that case.

Sometimes an assumption is quietly load-bearing. Dijkstra's 1959 shortest-path algorithm is greedy: repeatedly finalise the nearest unfinalised vertex. That is correct only because edge weights are non-negative, which is what makes distances monotone along a path. Introduce a single negative edge and a vertex you already finalised can later be improved. The repair is not a better greedy rule, it is a different technique: Bellman-Ford relaxes every edge $|V|-1$ times, and it is dynamic programming.

Trying examples is not evidence, but for restricted families the question is genuinely decidable.

Change-making is the clean case. Given a set of coin denominations, is the greedy algorithm optimal for every target? Chang and Gill gave a procedure polynomial in the size of the largest coin; Kozen and Zaks asked whether one exists that is polynomial in the size of the input. Pearson answered yes in Operations Research Letters in 2005, by characterising the smallest counterexample and showing it must lie among $O(n^2)$ candidate values for $n$ denominations. Test those, and you know.

Two things are worth separating here. Deciding whether greedy is optimal for a coin system is polynomial. Actually making optimal change in an arbitrary system is NP-hard. So a cheap test tells you whether you may use the cheap algorithm, and when the answer is no, you fall back to dynamic programming.