Non-overlapping Intervals

Problem

A task scheduler receives jobs with [start, end] time windows. Some jobs conflict - their windows overlap. The scheduler must find the minimum number of jobs to drop so the remaining set can all run without conflict. Given a list of intervals, return the minimum number of intervals to remove to make the rest non-overlapping.

Input: [[1,2],[2,3],[3,4],[1,3]]  ->  1  (remove [1,3])
Input: [[1,2],[1,2],[1,2]]        ->  2  (keep one, drop two)
Input: [[1,2],[2,3]]              ->  0  (touching boundary, not overlapping)

Solution

Approach: classic interval scheduling - sort by end time, greedily keep the earliest-finishing interval.

Reframe the problem: minimizing removals is the same as maximizing how many intervals you keep, since removed = total - kept. To keep the most non-overlapping intervals, sort by end time and greedily accept each interval that starts at or after the last one you kept. Track last_end, initialized to negative infinity so the first interval is always accepted. For each [start, end], if start >= last_end it does not collide with the last kept interval, so keep it and advance last_end = end. Otherwise it overlaps - discard it with removals += 1 and, crucially, leave last_end untouched, because the interval you kept finishes earlier and blocks fewer future intervals.

Sorting by end time is the provably correct ordering: the earliest-finishing interval leaves the widest remaining window, so keeping it can never lose. The exchange argument seals it - if an optimal solution kept some other interval, swapping in the earliest-ending one ends no later and so blocks no more, leaving the count at least as high. Trace [[1,2],[2,3],[3,4],[1,3]] sorted by end -> [1,2],[2,3],[1,3],[3,4]: keep [1,2] (end 2), keep [2,3] (2 >= 2, end 3), [1,3] has 1 < 3 so remove, keep [3,4] (3 >= 3). One removal.

Edge cases: an empty list returns 0 up front; touching intervals (start == last_end) are not overlaps because the test is >=; identical duplicates all overlap, so n copies cost n-1 removals.

Complexity: O(n log n) time from the sort, O(n) scan; O(1) extra space beyond the sort.