The problem. Given an array of intervals, return the minimum number of intervals to remove so that the rest don't overlap. Intervals that only touch, like [1,2] and [2,3], don't overlap.
[[1,2], [2,3], [3,4], [1,3]] -> 1 (remove [1,3])
[[1,2], [1,2], [1,2]] -> 2
[[1,2], [2,3]] -> 0Removing as few as possible is the same as keeping as many as possible. Among all intervals, the one that ends earliest is always a safe first choice: whatever the best answer keeps first, swapping it for the earliest-ending interval can't cause a new overlap, because that one ends even sooner. After choosing it, discard everything that overlaps it and repeat with what's left.
Sorting by end time turns that into one pass: walk the intervals in order of end, keep an interval if it starts at or after the end of the last one kept, and skip it otherwise. This is the classic interval scheduling greedy.
A safe but slower route: sort by start, and let keep[i] be the most intervals that can be kept ending with interval i — one plus the best keep[j] over earlier intervals j that end by the time i starts.
function eraseOverlapIntervals(intervals) { const a = [...intervals].sort((x, y) => x[0] - y[0]); // by start time const keep = new Array(a.length).fill(1); let most = 0; for (let i = 0; i < a.length; i++) { for (let j = 0; j < i; j++) { if (a[j][1] <= a[i][0]) keep[i] = Math.max(keep[i], keep[j] + 1); // i can follow j } most = Math.max(most, keep[i]); } return a.length - most;}Time O(n²), space O(n). Correct, but it considers every pair.
Sorted by end time, keep an interval whenever it starts after the last kept one ends.
function eraseOverlapIntervals(intervals) { const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // by end time let kept = 0, lastEnd = -Infinity; for (const [start, end] of sorted) { if (start >= lastEnd) { // fits after the last kept interval: keep it kept++; lastEnd = end; } // otherwise it overlaps: remove it } return sorted.length - kept;}Time O(n log n), space O(n) for the copy. One pass after the sort.
Sorting by start and keeping greedily doesn't work: [1,100] starts first but blocks everything. Sorting by end is the whole trick.
[1,2] and [2,3] both stay: compare with >=.lastEnd below any possible start.