Non-overlapping Intervals medium

Description

Given an array of intervals intervals where intervals[i] = [start, end], return the minimum number of intervals you need to remove to make the rest non-overlapping.

Examples

> Case 1:
    intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
    Output: 1
    # Remove [1, 3] — the remaining [1,2], [2,3], [3,4] don't overlap.
 
> Case 2:
    intervals = [[1, 2], [1, 2], [1, 2]]
    Output: 2
    # Keep one, remove the other two.
 
> Case 3:
    intervals = [[1, 2], [2, 3]]
    Output: 0
    # Already non-overlapping (touching at endpoints doesn't count).

Constraints

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 · 10^4 <= start < end <= 5 · 10^4

Flip the question

“Minimum to remove” sounds tricky. Flip it: “maximum to keep”. If we can find the largest non-overlapping subset of size k, the answer is n − k.

That’s exactly Activity Selection from the classics page! Sort by end time, greedily pick non-overlapping intervals, count them.

The greedy

1. Sort intervals by end time (ascending).
2. Walk through. Keep the current interval if its start >= last kept end. Otherwise, it overlaps — skip (= remove).
3. Return the count of skipped intervals.

Code

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b) { return a[1] < b[1]; });
    int removed = 0;
    int last_end = INT_MIN;
    for (auto& iv : intervals) {
        if (iv[0] >= last_end) {
            last_end = iv[1];                 // keep this one
        } else {
            removed++;                         // overlaps — remove
        }
    }
    return removed;
}

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    removed = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            last_end = end
        else:
            removed += 1
    return removed

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int removed = 0;
    int lastEnd = Integer.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= lastEnd) {
            lastEnd = iv[1];
        } else {
            removed++;
        }
    }
    return removed;
}

Why sort by end time?

Sorting by earliest end time maximizes the “room left” for the rest of the intervals. Counter-intuitively, sorting by start time or duration doesn’t work — see the introduction’s six-strategy comparison.

The exchange-argument proof: if an optimal solution picks an interval with a later end time when a non-overlapping interval with an earlier end time is available, swap them. The swap doesn’t create new overlaps (the earlier end leaves at least as much room) and the count is unchanged. Repeat until the optimum matches the greedy.

Sort by end, not by [start, end]

A common mistake: sorting by both start and end (the default tuple order). For this problem, sort only by end to maintain the invariant.

The interval family

Same template, slightly different per-step rules:

All five are variations on the “sort by end, sweep” idea.

Edge case: empty input

if not intervals: return 0

Strictly the constraints guarantee n >= 1, but defensive coding never hurts.

Analysis

• Time: O(n log n) — dominated by the sort.
• Space: O(1) extra.