Non-overlapping Intervals

medium intervals greedy sorting

Problem

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Inputintervals = [[1,4],[2,3],[3,5],[1,2]]

Output1

Sorted by end: [1,2], [2,3], [1,4], [3,5]. Keep [1,2], [2,3], [3,5]; drop [1,4].

intervals (e.g. "1,4; 2,3; 3,5; 1,2")

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    kept = 0
    end = float('-inf')
    for s, e in intervals:
        if s >= end:
            kept += 1
            end = e
    return len(intervals) - 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;
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int kept = 0, end = Integer.MIN_VALUE;
        for (int[] iv : intervals) {
            if (iv[0] >= end) { kept++; end = iv[1]; }
        }
        return intervals.length - kept;
    }
}

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

Explanation

We want to throw away as few intervals as possible so the rest never overlap. Instead of deciding what to remove, it is easier to decide what to keep: the fewer we remove, the more we keep, so we greedily keep the largest non-overlapping set.

The key insight is to sort by end time. Among all candidates, always keeping the one that ends earliest leaves the most room for the intervals that follow. This greedy choice is provably optimal.

We track end, the finish time of the last interval we kept. Walking through the sorted list, if an interval's start s is at or after end, it does not overlap, so we keep it and update end. Otherwise it overlaps and we skip it (effectively removing it).

Example: [[1,4],[2,3],[3,5],[1,2]] sorts by end into [1,2], [2,3], [1,4], [3,5]. Keep [1,2] (end=2), keep [2,3] (end=3), [1,4] starts at 1 < 3 so drop it, keep [3,5]. We kept 3, so removals = total - kept = 1.

The answer is simply len(intervals) - kept. Sorting dominates the cost, giving O(n log n).

Time: O(n log n) Space: O(1) beyond the sort