Write erase_overlap_intervals(intervals: list[list[int]]) -> int.
Each interval is [start, end] with start < end. Return the minimum number of intervals to remove so that no two of the remaining intervals overlap. Intervals that only touch, like [1, 3] and [3, 6], do not overlap.
Example: [[1, 3], [2, 4], [3, 5], [1, 2]] gives 2. Keep [1, 2], [2, 4] (or [1, 2], [3, 5]).
More examples: [[0, 5], [5, 10]] gives 0, and an empty list gives 0.
Constraints: up to 10^5 intervals, endpoints between -5 * 10^4 and 5 * 10^4.
⭐ Bonus: a speed test with 100,000 intervals earns a star in O(n log n). Comparing all pairs, or an O(n²) DP, is too slow for it.
Show hint
removing the fewest is the same as keeping the most. Among the intervals you could keep next, which one leaves the most room for the rest?