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.

Example 1:

Input: [[2,4],[4,6],[6,8],[2,6]]
Output: 1
Explanation: Remove [2,6]; the rest do not overlap.

Example 2:

Input: [[3,5],[3,5],[3,5]]
Output: 2
Explanation: Two duplicates must be dropped, keeping one.

Example 3:

Input: [[2,4],[4,6]]
Output: 0
Explanation: Touching boundaries are not overlapping, so nothing is removed.

Constraints:

• 0 <= intervals.length <= 5000
• intervals[i].length == 2
• -1000 <= start < end <= 1000

Solution Breakdown

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 [[2,4],[4,6],[6,8],[2,6]] sorted by end -> [2,4],[4,6],[2,6],[6,8]: keep [2,4] (end 4), keep [4,6] (4 >= 4, end 6), [2,6] has 2 < 6 so remove, keep [6,8] (6 >= 6). 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.