Algorithms / Greedy Stay Ahead
Least You Need to Know: Stay-Ahead Proofs for Greedy Algorithms
A stay-ahead proof compares the greedy solution with any competing solution across prefixes or steps and shows the greedy one never falls behind on a chosen progress measure. Instead of swapping a single decision, the proof establishes an invariant like 'after `i` picks, greedy has reached at least as far' or 'used no more resources so far.'
The least you need to know
- A stay-ahead proof tracks a measurable notion of progress across steps or prefixes.
- The greedy algorithm must be shown to be at least as good as any competitor on that measure at every step.
- The proof depends on the right progress metric.
- Greedy and competitor solutions do not need to choose identical objects.
- Stay-ahead is common when prefix progress matters more than single-choice substitution.
Key notation
prefix invariant
a statement comparing greedy and any competitor after the first `i` steps
progress measure
the quantity used to say greedy stays ahead
stay ahead
greedy is never worse on the comparison metric
Tiny worked example
- Suppose a greedy covering algorithm always extends coverage as far right as possible.
- Compare it against any other solution after the first `i` chosen intervals.
- Show greedy's covered right endpoint is at least as far.
- Therefore greedy never falls behind and can finish with no more intervals than a competitor.
Common mistakes
- Picking the wrong progress metric can make a correct greedy algorithm look unprovable.
- Stay-ahead proofs compare prefixes, not just the final answers.
- The competing solution need not copy greedy choices exactly.
How to recognize this kind of problem
- The proof compares greedy progress step by step against any alternative.
- There is a natural prefix quantity such as covered distance, completion time, or resource usage.
- You are not swapping one object into an optimal solution; you are maintaining a global comparison invariant.