Greedy Choice and the Exchange Argument
A greedy method takes the locally best option and never reconsiders. It can be correct even before a proof is found, but a proof is what shows it is correct, 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 one room, the aim is to fit the most activities, with each activity worth the same and no two overlapping. Starting exactly when another ends is not overlapping. The rule is to take the earliest-finishing activity that starts at or after the last pick ends, and repeat with the activities that start at or after it ends.
The rule is only safe with a proof. Take any best schedule and swap its first pick for the earliest-finishing one. The swap ends no later, so every later activity in the best schedule still fits, starting at or after it ends, and the count never drops. The rest is the same problem on the activities that start at or after that finish, so the swap argument applies again to the remaining compatible activities. 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.
For one room, earliest finish among compatible activities wins the most activities when swaps prove it, and coin traps warn you to prove first.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Nothing; this is a starting point.
Optional connections
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.