Lesson 15.3 · Intervals
Sort by End for Greedy Choices
To keep the most non-overlapping intervals, always pick the one that ends earliest: it leaves the most room for the rest.
12 min
Think of it like this
Fitting as many short talks as possible into one hall: at each step choose the talk that finishes first among those you can still fit. Finishing early never blocks more future talks than finishing late would.
1.Why earliest end is safe
Exchange argument: take any optimal selection. Its first interval ends no earlier than the earliest-ending interval overall. Swapping it for the earliest-ending one keeps everything after it compatible and the count the same. Repeat for each step, and the greedy selection is optimal too.
This solves activity selection, non-overlapping intervals (remove the fewest) and minimum arrows to burst balloons.
Remember
- Max non-overlapping set: sort by end, take each compatible interval.
- Fewest removals = n − maximum kept.
- Prove greedy choices with an exchange argument.
Common mistakes
- Sorting by start for selection problems (a long early interval blocks many short ones).