Non-overlapping Intervals

Problem Statement

Given a collection of intervals [start, end], find the minimum number of intervals to remove to make the rest non-overlapping. This medium-level greedy problem is like scheduling—keep as many events as possible without conflicts!

Example

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1 (remove [1,3])

Input: intervals = [[1,2],[1,2],[1,2]]

Output: 2 (remove two [1,2]s)

Code

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                count++;
            } else {
                end = intervals[i][1];
            }
        }
        return count;
    }
}
            

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] < end:
            count += 1
        else:
            end = intervals[i][1]
    return count
            

function eraseOverlapIntervals(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let count = 0;
    let end = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < end) {
            count++;
        } else {
            end = intervals[i][1];
        }
    }
    return count;
}
            

Explanation

• Greedy Choice: Sort by end time, keep the interval ending earliest.
• Flow: Count overlaps to remove when start times conflict with the current end.
• Example: [[1,2],[1,3],[2,3],[3,4]] → keep [1,2], remove [1,3], keep [2,3],[3,4].

Note