Non-overlapping Intervals [Medium] — Greedy Scheduling

Problem Statement

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

Input: [[1,2],[2,3],[3,4],[1,3]] → Output: 1 (remove [1,3])

Intuition

Classic greedy: sort by end time. Keep track of the previous end. If the current start < previous end, it overlaps — remove it (count++). Otherwise update previous end.

Solutions

C++

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

Java

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

JavaScript

var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a,b) => a[1]-b[1]);
    let count = 0, prevEnd = -Infinity;
    for (const [s,e] of intervals) {
        if (s < prevEnd) count++;
        else prevEnd = e;
    }
    return count;
};

Python

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    count, prev_end = 0, float('-inf')
    for s, e in intervals:
        if s < prev_end:
            count += 1
        else:
            prev_end = e
    return count

Complexity

Time: O(n log n)
Space: O(1)