Greedy Stays Ahead
Motivation
A greedy algorithm builds a solution one piece at a time, always taking the locally best option without backtracking. Whenever a greedy algorithm is correct, something must explain why never reconsidering is safe. Greedy stays ahead is one of the two standard proof templates for that explanation (the other is the exchange argument).
The idea is to track a numerical measure of “progress” through the input — items selected, time elapsed, distance covered — and show, by induction, that after each step the greedy solution is at least as far along as any optimal solution. Once the greedy is no worse on every prefix, it cannot be worse overall. This pattern shows up in interval scheduling, shortest-path algorithms, minimum spanning trees, and many other settings (Kleinberg and Tardos 2005).
The template
Let \(G = (g_1, g_2, \dots, g_k)\) be the sequence of items the greedy commits to, in the order it picks them. Let \(O = (o_1, o_2, \dots, o_m)\) be the corresponding sequence from any optimal solution, ordered the same way (e.g., by finish time, by distance, by index).
Pick a “progress” measure \(\phi\) — a function of the prefix that captures how much room is left for future commitments. Typical choices:
- finish time of the last interval picked,
- shortest-path distance to a node,
- weight of the lightest edge crossing a frontier.
The proof has two steps:
Lemma (stays ahead). For every \(r \le \min(k, m)\), \(\phi(g_1, \dots, g_r) \le \phi(o_1, \dots, o_r)\) — the greedy prefix is at least as good (less constrained, closer, lighter) as the optimal prefix.
Proof by induction on \(r\). The base case \(r=1\) uses the greedy’s first choice being globally extremal. For the inductive step, by hypothesis the greedy prefix is no worse than the optimal one, so every candidate available to the optimal at step \(r\) is also available to the greedy. The greedy picks the locally best among these, so \(\phi\) stays ahead.
Theorem (no shorter optimum). \(k \ge m\).
Proof. If \(k < m\), then \(o_{k+1}\) exists. The “stays ahead” lemma at \(r = k\) shows that the greedy could have extended its solution with \(o_{k+1}\), contradicting termination.
Canonical example: interval scheduling
Interval scheduling: given \(n\) intervals, select a maximum-size pairwise non-conflicting subset.
The greedy picks the interval with the earliest finish time, then repeats among intervals starting at or after that finish. Take \(\phi\) to be the finish time of the last selected interval. At every step \(r\), the greedy’s \(r\)-th finish is no later than the optimum’s \(r\)-th finish, so the greedy never falls behind in available room. If the optimum had more intervals, the greedy could have picked one too.
Example: interval scheduling stays-ahead proof
Five intervals sorted by finish time (the greedy sort key):
| Interval | Start | Finish |
|---|---|---|
| 1 | 0 | 2 |
| 2 | 1 | 3 |
| 3 | 2 | 5 |
| 4 | 4 | 6 |
| 5 | 5 | 7 |
Greedy selects 1 (ends at 2), skips 2 (starts at 1 < 2), selects 3 (starts at 2 ≥ 2), skips 4 (starts at 4 < 5), selects 5 (starts at 5 ≥ 5). Output: \(G = \{1, 3, 5\}\), \(|G|=3\).
Suppose an optimal solution is \(O = \{2, 4, 5\}\), also size 3. We verify the stays-ahead lemma at each \(r\):
| \(r\) | Greedy’s \(r\)-th interval | Its finish | Optimal’s \(r\)-th interval | Its finish | \(f(g_r) \le f(o_r)\)? |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 3 | \(2 \le 3\) ✓ |
| 2 | 3 | 5 | 4 | 6 | \(5 \le 6\) ✓ |
| 3 | 5 | 7 | 5 | 7 | \(7 \le 7\) ✓ |
At each step the greedy’s last finish time is no later than the optimum’s, so the greedy never “uses up” the timeline faster than the optimum does. Since both have \(r=3\) intervals and neither can extend (no remaining interval starts ≥ 7), neither solution is improvable: \(|G| = |O| = 3\).
Other examples
- Dijkstra’s algorithm (what): the \(r\)-th node finalized has shortest-path distance no larger than the \(r\)-th node finalized by any “correct” alternative ordering. The progress measure is the tentative distance.
- Minimum spanning tree (Kruskal, Prim): the \(r\)-th edge added has weight no greater than the \(r\)-th edge of any optimal spanning tree, when both are sorted by weight.
- Huffman coding: the partial code built after \(r\) merges has total weighted depth no greater than that of any optimal prefix of merges.
When stays-ahead does not work
Stays-ahead requires a scalar per-step measure that aligns with optimality. Some greedy proofs do not fit this mold:
- Minimizing maximum lateness (what): the natural per-step quantity (lateness of the \(r\)-th job) is not monotone, and the greedy’s \(r\)-th job may finish later than the optimum’s. The right proof is an exchange argument on inversions instead.
- Optimal caching with farthest-in-future (what): no obvious “progress” scalar; the proof exchanges eviction decisions.
A useful heuristic: if the greedy choice rule sorts inputs by a scalar key and the objective is “how many” or “how far,” try stays-ahead first. If the objective is “minimize the maximum” or “minimize total cost over a permutation,” try the exchange argument.