Non-overlapping Intervals

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}