The Greedy Method

A greedy algorithm builds up a solution piece by piece, and at every step it takes the option that looks best right now (the largest, the smallest, the cheapest, the soonest) with no regard for the choices still to come and no willingness to revisit a choice already made. It is the algorithmic embodiment of optimism: grab the locally optimal thing and trust that it adds up to a globally optimal whole.

Sometimes that optimism is justified, and the result is an algorithm of astonishing simplicity and speed. Sometimes it is naive, and the algorithm returns confidently wrong answers. The entire art of the greedy method is telling the two cases apart, and the only way to know you are in the good case is to prove it. Erickson puts the warning bluntly: most greedy algorithms are wrong, and a greedy strategy that has not been proved correct should be treated as a plausible guess, nothing more.¹

What makes greedy work

Dynamic programming, which we meet in a later module, considers all the ways a problem decomposes and picks the best. Greedy algorithms are bolder: they commit to one choice immediately and recurse on what remains. Two structural properties are what license that boldness.

• The greedy-choice property.² There exists an optimal solution that contains the greedy (locally optimal) first choice. We never have to look ahead: a best-looking-now choice is safe, since some optimal solution agrees with it.
• Optimal substructure. After making the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to the whole is the greedy choice plus an optimal solution to that subproblem.

Optimal substructure is shared with dynamic programming. The greedy-choice property is the extra gift: it collapses the many subproblems DP would explore down to a single one. That is why greedy algorithms, when they work, are so much faster than their DP cousins. Proving these two properties, not running the code on a few examples, is what separates a correct greedy algorithm from a hopeful heuristic.

The canonical example: activity selection

Here is the problem on which to build all intuition. We are given $n$activities that all want the same resource: a lecture hall, a tennis court, a single CPU. Activity $i$ has a start time $s_i$ and a finish time $f_i$, and occupies the half-open interval $[s_i,f_i)$. Two activities are compatible if their intervals do not overlap. We want to select a largest possible set of mutually compatible activities.

Drawn on a number line, an instance and one optimal schedule look like this. The shaded bars are the chosen activities; they tile the timeline without overlap.

The chosen set $\{a,c,e,g\}$ uses four activities; no compatible set is larger. The question is which greedy rule finds such a set.

Choosing the right greedy rule

Several plausible rules suggest themselves, and most are wrong:

• Earliest start first? A single activity that starts at time $0$ but runs forever blocks everything — wrong.
• Shortest duration first? A short activity wedged between two longer ones can knock out two compatible activities to gain one — wrong.
• Fewest conflicts first? Tempting, but constructible counterexamples defeat it too.

Two of these failures are easy to picture. Earliest-start picks the long bar that hogs the whole timeline; shortest-job picks the little wedge that destroys both of its neighbors.

The rule that works is earliest finish time first: repeatedly pick the compatible activity that finishes soonest.³ The intuition is resource-centric: finishing early frees the hall as soon as possible, leaving the most room for everything that follows. This is the heart of interval scheduling.

After the one-time sort by finish time, a single linear scan does the rest: $\Theta (n)$ work, for $\Theta (n\log n)$ total, dominated entirely by the sort. If the finish times arrive already sorted, the selection itself is linear.

Correctness by the exchange argument

The usual proof technique for greedy algorithms is the exchange argument: take any optimal solution, and show you can transform it, swapping one of its choices for the greedy choice, without making it worse. Since the result is no worse, it is still optimal, and it now agrees with greedy on the first choice. That establishes the greedy-choice property; optimal substructure then finishes the job by induction.

The picture of the swap is the whole argument in one image. Activity $1$ slides in where $j$ was, finishing at least as early, so nothing downstream can break.

With the greedy-choice lemma in hand, optimal substructure completes the proof by induction. After committing to activity $1$, every remaining feasible activity must start at or after $f_1$; the leftover problem is just activity selection on that smaller set, which the same rule solves optimally by the induction hypothesis. The greedy choice plus the optimal subsolution is optimal for the whole. $■$

This two-step shape, (1) an exchange argument for the greedy-choice property and (2) induction via optimal substructure, is the template for every greedy correctness proof in this course, Huffman codes and minimum spanning trees included.

When greedy fails: the 0/1 knapsack

Greed is not a universal solvent, and the cleanest way to feel its limits is the knapsack problem. We have a knapsack of capacity $W$ and $n$ items, item $i$ having weight $w_i$ and value $v_i$. We want the most valuable load that fits.

In the fractional knapsack, we may take any fraction of an item. Here greed works perfectly: sort by value density $v_i/w_i$, and greedily fill with the densest item, taking a fraction of the last one to top off the capacity exactly.⁴ An exchange argument proves it: any optimal solution that takes less of a denser item and more of a sparser one can be nudged toward the greedy choice without losing value.

In the 0/1 knapsack, each item is all-or-nothing: take it whole or leave it. And here the same density rule collapses. Consider $W=10$ and:

Greedy by density grabs item $1$ (value $12$, weight $6$), then cannot fit either remaining item, since both need weight $5$ but only $4$ is left. It returns value $12$. Yet items $2$ and $3$ together weigh exactly $10$ and are worth $18$. Greedy loses by a mile.

This is exactly the boundary between greedy and dynamic programming. The 0/1 knapsack has optimal substructure but lacks the greedy-choice property, so it needs DP, which considers both alternatives (take item $i$ or skip it) rather than committing to one. The fractional version restores the greedy-choice property because a fraction can always absorb the leftover capacity exactly, leaving no stranded space to regret.

When is greed good? A glimpse of matroids

It would be wonderful to have a theorem of the form greedy is optimal exactly when…. For a large and important family of problems, such a theorem exists, and its language is the matroid.

A matroid is a pair $(E,\mathcal{I})$ built from a finite ground set $E$ and a family $\mathcal{I}$ of independent subsets, satisfying two axioms:

• Heredity. If $A\in \mathcal{I}$ and $B\subseteq A$, then $B\in \mathcal{I}$. (Subsets of independent sets are independent.)
• Exchange. If $A,B\in \mathcal{I}$ and $\left|A\right|<\left|B\right|$, then some element $x\in B\setminus A$ has $A\cup \left\{x\right\}\in \mathcal{I}$. (A smaller independent set can always be grown using an element of a larger one.)

The forests of a graph form a matroid: subsets of a forest are forests, and a smaller forest can always borrow an edge from a larger one without making a cycle.

The headline result, due to Rado and Edmonds, is that the greedy algorithm computes a maximum-weight independent set if and only if the structure is a matroid.⁵ That single theorem is the deep reason Kruskal's minimum spanning tree algorithm, which greedily adds the cheapest edge that creates no cycle, is correct: it is greedy on the graphic matroid. Activity selection, too, is greedy on a matroid in disguise.

Matroids do not cover every successful greedy algorithm. Huffman coding, our next lesson, lives outside the theory, yet they explain a remarkable swath of them and turn does greed work here? from an art into, sometimes, a checkable condition. We will not develop the theory further here; the point is that there is a theory, and the exchange axiom that defines it is the same exchange idea that powers our correctness proofs.

A recipe for greedy algorithms

Drawing the three books together, the workflow is always the same:

1. Cast the problem as a sequence of choices, where each choice leaves a smaller subproblem of the same kind.
2. Guess a greedy rule — the locally optimal choice. Beware: the obvious rule is often wrong (recall the failed activity-selection rules).
3. Prove the greedy-choice property with an exchange argument: any optimal solution can be massaged to contain the greedy choice.
4. Prove optimal substructure and combine, by induction, into a full proof.

If steps 3 and 4 go through, you have a correct, usually fast, usually simple algorithm. If they do not, you have learned something too: reach for dynamic programming instead.

Takeaways

• A greedy algorithm makes the locally optimal choice at each step and never reconsiders. It is fast and simple, when it is correct.
• Correctness needs two properties: the greedy-choice property (some optimal solution contains the greedy choice) and optimal substructure (what remains is the same problem, smaller).
• Activity selection by earliest finish time is the canonical win; its proof is the template exchange argument plus induction. Cost: $\Theta (n\log n)$, all in the sort.
• The 0/1 knapsack is the canonical failure: it lacks the greedy-choice property, so greed strands capacity and needs dynamic programming instead. Its fractional cousin restores the property and yields to greed.
• Matroids characterize a broad class where greedy is provably optimal (Kruskal's MST among them), the formal echo of the exchange argument itself.