Non-overlapping Intervals
Problem
Return the minimum number of intervals to remove so that the rest do not overlap. Intervals that only touch, like [1,2] and [2,3], do not overlap.
Example 1
Input: [[1,2], [2,3], [3,4], [1,3]] Output: 1
Remove [1,3].
Example 2
Input: [[1,2], [1,2], [1,2]] Output: 2
Test cases
Case 1
Input: [[1,2],[2,3],[3,4],[1,3]] Expected: 1
Case 2
Input: [[1,2],[1,2],[1,2]] Expected: 2
Case 3
Input: [[1,2],[2,3]] Expected: 0
View solutionHide solution1 approach
1. Sort by end, keep the earliest-finishing
Time O(n log n)Space O(1) extra
Activity selection: keeping the interval that ends first leaves the most room. Removals = total − kept.
function eraseOverlapIntervals(intervals) { intervals.sort((a, b) => a[1] - b[1]); let kept = 0, end = -Infinity; for (const [s, e] of intervals) { if (s >= end) { kept++; end = e; } } return intervals.length - kept;}