249. Non-Overlapping Intervals

Sort by start time. When two intervals overlap, remove the one that extends further (larger end) since it is more likely to overlap with future intervals.

Brute Force (Greedy by Start)

Sort intervals by start time. Walk through the sorted list and whenever two consecutive intervals overlap, increment a removal counter and keep the interval with the smaller end time.

This works correctly and is actually O(n log n) due to sorting. The key difference from the optimal is purely stylistic — sorting by end is the classic formulation.

Complexity: O(n log n) time for sorting, O(1) extra space (ignoring sort internals).

import java.util.*;

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

The classic activity selection insight: always keep the interval that ends earliest, because it leaves the most room for future intervals.

Mental Model

Imagine booking meeting rooms. If two meetings conflict, you should cancel the one that runs later — the shorter meeting frees up the room sooner for the next one. Sorting by end time formalizes this: the interval that finishes earliest is always the best to keep.

Algorithm Steps

1. Sort intervals by their end time.
2. Set prev_end to the end of the first interval.
3. For each subsequent interval [s, e]:
   • If s < prev_end, it overlaps — increment removal count (we remove this interval, keeping the one with the earlier end).
   • Otherwise, update prev_end = e.
4. Return the removal count.

Worked Walk-through

intervals = [[1,2],[2,3],[3,4],[1,3]] -> sorted by end: [[1,2],[2,3],[1,3],[3,4]]

Answer: 1

Edge Cases

• Single interval: No overlaps possible, return 0.
• All identical intervals: Remove all but one, return n-1.
• No overlaps: Return 0.

Complexity

• Time: O(n log n) for sorting, then O(n) for the sweep.
• Space: O(1) extra space beyond the sort.