Non-overlapping Intervals
Last Updated: March 29, 2026
Understanding the Problem
We have a collection of intervals on a number line, and some of them overlap. Our job is to figure out the fewest intervals we can throw away so that no two remaining intervals share any interior points. Two intervals touching at exactly one point (like [1,2] and [2,3]) are fine.
Think of it like scheduling meetings in a single conference room. Each interval is a meeting time. If two meetings overlap, we have to cancel one. The question is: what's the minimum number of meetings to cancel so everything fits without conflict?
The key observation is that "minimum removals" is the same as "maximum intervals we can keep." If we can find the largest set of non-overlapping intervals, then the number of removals is simply the total count minus that maximum set size. This reframes the problem into the classic "Activity Selection" problem from greedy algorithms.
Key Constraints:
1 <= intervals.length <= 10^5→ With n up to 100,000, an O(n^2) solution would be too slow. We need O(n log n) or better.-5 * 10^4 <= start_i < end_i <= 5 * 10^4→ Intervals can have negative start/end values. The strict inequality guarantees every interval has positive length.intervals[i].length == 2→ Each interval is exactly a pair. No degenerate inputs to worry about.
Approach 1: Greedy (Sort by Start)
Intuition
A natural first thought: sort the intervals by their start time, then walk through them left to right. If the current interval overlaps with the previous one we kept, we need to remove one of them. But which one should we remove?
Here's the key insight: when two intervals overlap, we should remove the one that extends further to the right (has the larger end value). Why? Because keeping the one with the smaller end value leaves more room for future intervals to fit without conflict. It's a greedy choice: always keep the interval that "finishes sooner."
So the algorithm becomes: sort by start, track the end of the last kept interval, and whenever we see an overlap, keep whichever interval ends earlier and count one removal.
When two intervals overlap, the greedy choice is always to keep the one that finishes earlier. The interval with the smaller end value "uses up" less of the number line, giving future intervals the best chance of fitting in without conflict. This is the essence of the Activity Selection problem: by always choosing the activity that finishes first, you maximize the number of activities you can schedule.
Sorting by start time ensures we process intervals left-to-right, so we never miss an overlap. And the min(prevEnd, end) update handles the case where a later-starting interval is entirely contained within a previous one.
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 works, but the overlap resolution requires a min comparison to decide which interval to keep. What if we sorted by end time instead, so the greedy choice becomes automatic?
Approach 2: Greedy (Sort by End) - Optimal
Intuition
Here's a cleaner way to think about the same greedy idea. Instead of sorting by start time and deciding which overlapping interval to remove, sort by end time. Now the greedy choice becomes trivially simple: always keep the next interval that starts at or after the previous kept interval's end.
Why does sorting by end time simplify things? Because the interval that ends earliest is always the best to keep. When we sort by end, the first non-overlapping interval we encounter is automatically the one that ends soonest. There's no need to compare ends and pick the minimum. We just keep or skip.
This is exactly the classic Activity Selection algorithm. The proof of optimality is well-known: at each step, choosing the earliest-finishing compatible activity never leads to a worse outcome than any other choice. This means we can count how many intervals we keep, and the answer is n - kept.
This is the Activity Selection problem, one of the foundational greedy algorithms. The proof works by exchange argument: suppose there's an optimal solution that doesn't pick the earliest-ending compatible interval at some step. You can swap in the earlier-ending interval without creating new conflicts (since it ends sooner), so you get an equally good or better solution. By induction, the greedy approach is optimal.
The elegance of sorting by end time is that the greedy decision collapses to a single comparison: "Does this interval start after the previous one ends?" No tie-breaking, no choosing between overlapping intervals. The earliest-ending interval is always already at the front of our sorted order.
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.