Non-overlapping Intervals

Problem in plain words

You are given a list of intervals [start, end]. Remove as few intervals as possible so that none of the remaining ones overlap. Intervals that only touch at an endpoint, like [1, 3] and [3, 4], do not count as overlapping. Return how many you removed.

For example, from [[1, 2], [1, 3], [2, 3]] you remove [1, 3] only, so the answer is 1.

Intuition

Removing the fewest intervals is the same as keeping the most. Keeping the maximum number of non-overlapping intervals is the classic activity selection problem: always keep the interval that finishes earliest, because it leaves the most room for everything after it. Any optimal solution can swap its first interval for the earliest-ending one without creating an overlap, so the greedy choice is never worse. The activity selection lesson walks through this exchange argument.

Approach

1. Sort intervals by their end value.
2. Keep the first interval and set lastEnd to its end. Set kept = 1.
3. For each next interval, if its start is at least lastEnd, keep it: kept++ and lastEnd = end.
4. Otherwise it overlaps a kept interval; skip it (that counts as a removal).
5. Return n - kept.

Dry run

Input: [[1, 3], [2, 4], [3, 5], [1, 6]], already in end order.

Two intervals are kept, so 4 - 2 = 2 are removed.

Java solution

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1]));
        int kept = 1;
        int lastEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= lastEnd) {   // no overlap: keep it
                kept++;
                lastEnd = intervals[i][1];
            }
        }
        return intervals.length - kept;
    }
}

Python solution

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda iv: iv[1])
        kept = 1
        last_end = intervals[0][1]
        for start, end in intervals[1:]:
            if start >= last_end:   # no overlap: keep it
                kept += 1
                last_end = end
        return len(intervals) - kept

Complexity

Edge cases and common mistakes

• Touching endpoints: use >=, not >. [1, 2] and [2, 3] can both stay.
• Sorting by start: sorting by start alone fails on a long interval that begins first, such as [1, 100] before [2, 3] and [4, 5]; it would be kept and block the two short ones. (A start-sorted version works only if you keep the smaller end on each overlap.)
• Comparator overflow: in Java, x[1] - y[1] can overflow for extreme values. Integer.compare is always safe.
• Single interval: nothing overlaps and the answer is 0.