Erase the Fewest Overlapping Intervals

medium intervals greedy sorting

Problem

Given a list of intervals, return the minimum number you must remove so the rest don't overlap. Sort by end coordinate and greedily keep an interval whenever its start is at least the last kept end.

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.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 eraseOverlap(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 eraseOverlap(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 eraseOverlap(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;
}

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