Algorithms / Greedy Exchange Arguments
Least You Need to Know: Greedy Choice, Exchange Arguments, and Local Decisions
Greedy algorithms succeed when a locally optimal step can be justified as part of some globally optimal solution. Exchange arguments and staying-ahead arguments explain why taking a certain next move never makes the final answer worse.
Least you need to know
- A greedy algorithm makes one irrevocable local choice and then continues on the reduced problem.
- The key proof question is not speed but correctness: why is that local choice always safe?
- An exchange argument shows an optimal solution can be transformed to use the greedy choice without losing quality.
- A heuristic can look reasonable and still fail if there is no safety argument behind it.
- Greedy correctness usually depends on structure in the problem, not just intuition.
Key notation
- greedy choice — next local step taken immediately
- exchange argument — swap optimal solution pieces to include greedy step
- stays ahead — greedy partial solution is never worse than competitors so far
Worked example
- In interval scheduling, pick the interval that finishes earliest.
- If an optimal schedule starts with a later-finishing interval, swap that first interval with the greedy one.
- The greedy interval leaves at least as much room for the remaining intervals.
- So there exists an optimal schedule that begins with the greedy choice.
Common mistakes
- Students often call a method greedy just because it is fast, even without a proof that the local choice is safe.
- Students often confuse 'works on examples' with a correctness argument.
- Students often forget that some coin systems and scheduling rules break greedy intuition.
How to recognize it
- The problem can be reduced after one safe local choice.
- There is a natural candidate for an exchange or staying-ahead proof.
- You want one good optimum, not all valid combinations.
Next recommended lesson
Continue through this topic with Least You Need to Know: Grid Traversal, Flood Fill, and Boundary Checks.
Least You Need to Know: Grid Traversal, Flood Fill, and Boundary ChecksRelated lessons
Keep going with nearby lessons in the same topic.