Greedy Choice and the Exchange Argument
A greedy method takes the locally best option and never reconsiders. It is right only when a proof says so, and the usual proof takes any optimal solution and swaps its first choice for the greedy one without making it worse.
What a learner can do afterwards
- Solve interval scheduling greedily and prove the earliest-finish rule with an exchange
- Find a coin system where taking the largest coin first gives the wrong answer
- Say what property a problem must have before a greedy rule can be correct
1 · Read
A greedy method takes the locally best option and never looks back. For booking rooms, the rule is to take the activity that finishes earliest. That leaves the most room for the rest, and it gives the most activities you can fit.
The rule is only safe with a proof. Take any best schedule and swap its first pick for the earliest-finishing one. Nothing breaks, since the swap ends no later, and the count never drops. Repeat the swap and the greedy set matches a best one.
With coins of 1, 3, and 4, greedy grabs the largest first. For 6 it takes 4, 1, 1: three coins. Yet 3 plus 3 uses two. Largest-first fails here, which proves greedy needs checking every time.
Ask two things before trusting a greedy rule. Is the first grab always part of some best answer, and does the rest keep the same shape. If either fails, reach for another method.
Earliest finish wins rooms when swaps prove it, and coin traps warn you to prove first.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.