Why it works
- Removing the fewest is the same as keeping the most. Of all the intervals, the one that ends first is always worth keeping: any other choice ends later and leaves less room for the rest.
- After it, the same choice repeats on what starts at or after its end. Sorted by end, that is one pass: keep an interval if start ≥ lastEnd, otherwise it overlaps the last kept one, so remove it.
- Sorting by start would go wrong here: [0, 9] starts first, and keeping it would block [1, 3], [3, 5] and [6, 8].
Complexity
Time O(n log n): the sort; the pass after it is O(n). Memory O(1) besides what the sort needs.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗