Non-overlapping Intervals
Remove the fewest intervals so the rest do not overlap.
Why does this pattern fit?
Restate the exact job
Remove the fewest intervals so the rest do not overlap.
Keeping the interval that ends earliest leaves the most room for future intervals.
O(n log n) time · O(1) extra after sort
Keeping the earlier-starting interval can block more future choices.
How to solve Non-overlapping Intervals
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Remove the fewest intervals so the rest do not overlap.
Why Intervals & sweep line fits
Keeping the interval that ends earliest leaves the most room for future intervals.
State to maintain
Last kept end and removal count.
Transition
Sort by end; keep compatible intervals and count the others as removals.
Time and space
O(n log n) time · O(1) extra after sort
Counterexample to the tempting mistake
Keeping the earlier-starting interval can block more future choices.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.