Non-overlapping Intervals
Understanding the Problem
We have a collection of intervals on a number line, and some of them overlap. The goal is to remove the fewest intervals so that no two remaining intervals share any interior points. Two intervals touching at exactly one point (like [1,2] and [2,3]) are allowed.
A useful way to see it: each interval is a meeting that needs a single conference room. If two meetings overlap, one of them has to be cancelled. We want the minimum number of cancellations so the rest fit without conflict.
Minimizing removals is the same as maximizing how many intervals we keep. If we find the largest set of mutually non-overlapping intervals, the number of removals is the total count minus that maximum set size. This is the Activity Selection problem from greedy algorithms.
Key Constraints:
1 <= intervals.length <= 10^5→ With n up to 100,000, an O(n^2) solution is too slow. We need O(n log n) or better.-5 * 10^4 <= start_i < end_i <= 5 * 10^4→ Starts and ends can be negative, so any code that assumes non-negative coordinates is wrong. The strict inequality means every interval has positive length, so a degenerate point interval like[3,3]never appears.
Approach 1: Greedy (Sort by Start)
Intuition
Sort the intervals by start time and walk through them left to right, tracking the end of the last interval we decided to keep. When the current interval overlaps that kept interval, one of the two has to go. Remove the one with the larger end value and keep the one that finishes earlier.
Keeping the interval with the smaller end leaves more of the number line free for later intervals, so it can never reduce how many we fit afterward. That earliest-finish rule is the core of Activity Selection. Sorting by start guarantees we visit intervals in left-to-right order, so an overlap is always detected when start < prevEnd. The min(prevEnd, end) update also covers the case where the current interval is fully contained inside the previous one: we drop the wider previous interval and continue from the tighter end.
Algorithm
- Sort the intervals by their start value. If two intervals have the same start, sort by end value.
- Initialize
prevEndto the end of the first interval andremovals = 0. - For each subsequent interval
[start, end]: - If
start < prevEnd(overlap detected): - Increment
removals. - Update
prevEnd = min(prevEnd, end)(keep the interval that ends sooner). - Otherwise (no overlap):
- Update
prevEnd = end. - Return
removals.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n) and the single pass through the sorted array is O(n). The sorting step dominates.
- Space Complexity: O(1). We only use a few integer variables. The sorting is done in-place (excluding O(log n) stack space used by some sorting implementations).
The sort-by-start approach needs a min comparison on every overlap to decide which interval to keep. Sorting by end time removes that comparison: the next approach uses the same greedy idea but reads the answer off a single condition.
Approach 2: Greedy (Sort by End) - Optimal
Intuition
This is the same greedy idea with a different sort key. Sort by end time instead of start time, then keep the next interval whenever it starts at or after the previous kept interval's end.
Sorting by end time removes the min comparison from Approach 1. The interval that ends earliest is the best one to keep, and after sorting by end it is already at the front of whatever remains, so there is nothing to compare: each interval is either compatible with the last kept one or skipped. Count how many we keep, and the answer is n - kept.
The exchange argument shows the greedy choice is optimal. Take any optimal selection of non-overlapping intervals. If its first interval is not the one with the smallest end, replace it with the smallest-end interval. That swap is legal because the replacement ends no later, so it cannot conflict with anything the optimal solution kept after it. The selection size is unchanged. Repeating this argument for each subsequent choice shows the greedy selection matches an optimal one, so it is optimal.
Algorithm
- Sort the intervals by end value. If two intervals have the same end, their order doesn't matter.
- Initialize
prevEndto the end of the first interval andkept = 1(we keep the first interval). - For each subsequent interval
[start, end]: - If
start >= prevEnd(no overlap): - Keep this interval:
kept++, updateprevEnd = end. - Otherwise: skip it (it overlaps).
- Return
n - kept.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n) and the single pass through the sorted array is O(n). Total is O(n log n).
- Space Complexity: O(1). We use a constant number of variables. In-place sorting uses O(log n) stack space in most implementations.