Non-overlapping Intervals

mediumGreedy & Intervals19 stepsJava · Python · C++

Remove the fewest intervals so the rest don't overlap. Sort by end time and greedily keep each interval that starts at or after the last kept end. Keeping the earliest-ending interval leaves the most room for the rest.

▶ Watch the animated trace

Traced input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]] → 1. Original problem: neetcode.io/problems/non-overlapping-intervals

Complexity

BestO(n log n)

AverageO(n log n)

WorstO(n log n)

SpaceO(1)

Sorting dominates.

Key idea

This is activity selection: maximise kept intervals, then removed = n − kept.
Sort by end, not start.
Touching intervals ([1,2] and [2,3]) don't overlap here.

Common mistakes

Sorting by start and keeping the first can keep a long interval that blocks many.
Using > instead of >= treats touching intervals as overlapping.

Solution

Java

int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int kept = 0, lastEnd = Integer.MIN_VALUE;
    for (int i = 0; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            kept++;
            lastEnd = intervals[i][1];
        }
    }
    return intervals.length - kept;
}

Python

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda iv: iv[1])
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

C++

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    int kept = 0;
    long long lastEnd = LLONG_MIN;
    for (auto& iv : intervals) {
        if (iv[0] >= lastEnd) {
            kept++;
            lastEnd = iv[1];
        }
    }
    return intervals.size() - kept;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All identical Keep one.	`intervals = [[1, 2], [1, 2], [1, 2]]`	`2`
Already disjoint Touching is allowed.	`intervals = [[1, 2], [2, 3]]`	`0`
One long interval Removing the long one keeps two.	`intervals = [[1, 100], [2, 3], [4, 5]]`	`1`