Non-overlapping Intervals
MediumIntervals
You get a list of intervals, each [start, end]. Return the fewest intervals you must remove so that none of the remaining ones overlap.
Intervals that only touch, like [1, 3] and [3, 4], do not overlap.
Examples
Input: intervals = [[1, 3], [2, 5], [3, 4], [5, 6]] Output: 1
Removing [2, 5] leaves [1, 3], [3, 4] and [5, 6], which only touch.
Input: intervals = [[4, 8], [4, 8], [4, 8]] Output: 2
Three copies of one interval: keep one, remove two.
Constraints
1 ≤ intervals.length ≤ 10⁵-5 × 10⁴ ≤ start < end ≤ 5 × 10⁴
Stuck?
Hint 1
Count the most intervals you can keep instead. Among intervals that clash, keeping the one that ends first always leaves the most room.
Hint 2
Sort by end. Walk through, keeping an interval when it starts at or after the end of the last one kept, and counting it as removed otherwise.
The idea
Removing the fewest is the same as keeping the most. Among intervals that clash, the one that ends first leaves the most room for the rest. So sort by end, and keep each interval that starts at or after the end of the last one kept.
Time O(n log n)Extra space O(1) besides the sort
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Sort a copy by end time. Keeping the interval that ends first is never worse than keeping another one, so going through them in order of end lets the loop keep greedily.
function eraseOverlapIntervals(intervals) { const sorted = [...intervals].sort((a, b) => a[1] - b[1]); let removed = 0; let lastEnd = -Infinity; for (const [start, end] of sorted) { if (start >= lastEnd) lastEnd = end; else removed++; } return removed;}The trap
Sorting by start is the usual first move for intervals, and on a clash the code keeps the one it met first. But the one met first may end much later. A long interval that starts early covers several short ones that do not clash with each other; this keeps the long one and removes all the short ones, when removing the long one alone was enough.
function eraseOverlapIntervals(intervals) { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); let removed = 0; let lastEnd = -Infinity; for (const [start, end] of sorted) { if (start >= lastEnd) lastEnd = end; else removed++; // always drops the newcomer, even when it ends sooner } return removed;}