Non-Overlapping Intervals

Problem Statement

Given an array of intervals, return the minimum number of intervals you need to remove so the remaining set is pairwise non-overlapping.

Input

An array of intervals [[start, end], …].

[[1,2],[2,3],[3,4],[1,3]]
[[1,2],[1,2],[1,2]]

Output

A single integer — the minimum count of removals required.

1
2

Constraints

• 1 ≤ intervals.length ≤ 10⁵
• intervals[i].length == 2
• -5·10⁴ ≤ startᵢ < endᵢ ≤ 5·10⁴

Intuition

This is the Activity Selection Problem in disguise. By sorting by end time, we greedily keep the interval that finishes earliest — leaving the maximum room for future intervals. The number of removals equals total − max intervals we can keep.

After sort by END:  [[1,2], [2,3], [1,3], [3,4]]
 
Step 1  keep [1,2],   last_end = 2
Step 2  [2,3] → 2 ≥ 2 → no overlap → KEEP,   last_end = 3
Step 3  [1,3] → 1 < 3 → overlap    → REMOVE, count = 1
Step 4  [3,4] → 3 ≥ 3 → no overlap → KEEP
 
Answer:  1 removal

Solution

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
 
    # KEY: Sort by END time for greedy
    intervals.sort(key=lambda x: x[1])
 
    count = 0
    last_end = intervals[0][1]
 
    for i in range(1, len(intervals)):
        if intervals[i][0] < last_end:
            count += 1     # overlap → remove this one
        else:
            last_end = intervals[i][1]
 
    return count

function eraseOverlapIntervals(intervals: number[][]): number {
    if (intervals.length === 0) return 0;
 
    intervals.sort((a, b) => a[1] - b[1]);
 
    let count = 0;
    let lastEnd = intervals[0][1];
 
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < lastEnd) {
            count++;
        } else {
            lastEnd = intervals[i][1];
        }
    }
 
    return count;
}

Complexity

Edge Case Thinking