Non-overlapping Intervals
Problem
Given a collection of intervals, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
- 1 ≤ intervals.length ≤ 10⁵
- intervals[i].length == 2
- −5 * 10⁴ ≤ start_i < end_i ≤ 5 * 10⁴
Example
intervals = [[1,2],[2,3],[3,4],[1,3]]1A brute-force approach would check all subsets of intervals to find the largest non-overlapping set, which is exponential in time. Instead, the algorithm sorts intervals by start time and iterates through them, greedily deciding which intervals to keep or remove. For example, after sorting, intervals are [[1,2],[1,3],[2,3],[3,4]]. Starting with the first interval [1,2], the algorithm compares subsequent intervals. When it encounters [1,3], it overlaps with [1,2], so it removes one. It chooses to keep the interval with the earlier end time to maximize room for future intervals. This process continues, resulting in removing only one interval ([1,3]) to achieve a non-overlapping set.
Approach
Straightforward Solution
A brute-force approach tries all subsets of intervals to find the largest non-overlapping subset, which is O(2^n) and infeasible for large inputs.
Core Observation
The fundamental truth is that to minimize removals, one must maximize the number of non-overlapping intervals. Overlaps occur when the start of the current interval is less than the end of the previous chosen interval.
Path to Optimal
Sorting intervals by start time allows a linear scan to detect overlaps. When an overlap is found, removing the interval with the later end time preserves more space for future intervals, maximizing the count of non-overlapping intervals. This greedy choice is optimal because it leaves the earliest possible end time, increasing the chance that subsequent intervals fit without overlap.
Optimal Approach
Sort intervals by their start time. Initialize a variable to track the end of the last included interval. Iterate through intervals starting from the second one. If the current interval's start is at least the previous end, update the previous end to the current interval's end. Otherwise, increment the removal count and update the previous end to the minimum of the current and previous ends. Return the removal count after processing all intervals.
Time
O(n log n)
Sorting the intervals takes O(n log n). The subsequent single pass through the intervals is O(n), resulting in overall O(n log n) time.
Space
O(1)
The algorithm uses a constant amount of extra space for counters and pointers, not counting the input array.
Pattern Spotlight
Greedy Algorithms (Interval Scheduling)
When minimizing removals to avoid overlaps, always keep the interval with the earliest end time among overlapping intervals to maximize the remaining space for future intervals.
Solution
| 1 | class Solution:
|
| 2 | def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
|
| 3 | intervals.sort()
|
| 4 | res = 0
|
| 5 | prev_end = intervals[0][1]
|
| 6 |
|
| 7 | for start, end in intervals[1:]:
|
| 8 | if start >= prev_end:
|
| 9 | prev_end = end
|
| 10 | else:
|
| 11 | res += 1
|
| 12 | prev_end = min(end, prev_end)
|
| 13 |
|
| 14 | return res |
| 1 | import java.util.Arrays; |
| 2 | |
| 3 | class Solution { |
| 4 | public int eraseOverlapIntervals(int[][] intervals) { |
| 5 | Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); |
| 6 | int res = 0; |
| 7 | int prev_end = intervals[0][1]; |
| 8 | for (int i = 1; i < intervals.length; i++) { |
| 9 | int start = intervals[i][0]; |
| 10 | int end = intervals[i][1]; |
| 11 | if (start >= prev_end) { |
| 12 | prev_end = end; |
| 13 | } else { |
| 14 | res++; |
| 15 | prev_end = Math.min(end, prev_end); |
| 16 | } |
| 17 | } |
| 18 | return res; |
| 19 | } |
| 20 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int eraseOverlapIntervals(vector<vector<int>>& intervals) { |
| 9 | sort(intervals.begin(), intervals.end()); |
| 10 | int res = 0; |
| 11 | int prev_end = intervals[0][1]; |
| 12 | for (size_t i = 1; i < intervals.size(); ++i) { |
| 13 | int start = intervals[i][0]; |
| 14 | int end = intervals[i][1]; |
| 15 | if (start >= prev_end) { |
| 16 | prev_end = end; |
| 17 | } else { |
| 18 | res++; |
| 19 | prev_end = min(end, prev_end); |
| 20 | } |
| 21 | } |
| 22 | return res; |
| 23 | } |
| 24 | }; |
| 1 | var eraseOverlapIntervals = function(intervals) { |
| 2 | intervals.sort((a, b) => a[0] - b[0]); |
| 3 | let res = 0; |
| 4 | let prev_end = intervals[0][1]; |
| 5 | for (let i = 1; i < intervals.length; i++) { |
| 6 | let start = intervals[i][0]; |
| 7 | let end = intervals[i][1]; |
| 8 | if (start >= prev_end) { |
| 9 | prev_end = end; |
| 10 | } else { |
| 11 | res++; |
| 12 | prev_end = Math.min(end, prev_end); |
| 13 | } |
| 14 | } |
| 15 | return res; |
| 16 | }; |
Step-by-Step Solution
Sort Intervals by Start Time to Prepare for Greedy Selection
| 3 | intervals.sort()
|
Objective
To order intervals so that overlaps can be detected in a single pass by comparing adjacent intervals.
Key Insight
Sorting intervals by their start time arranges them in a sequence where any overlap must occur between consecutive intervals. This ordering is crucial because it allows the algorithm to detect and resolve overlaps efficiently without backtracking or complex data structures.
Interview Quick-Check
Core Logic
Sorting by start time ensures that any overlapping intervals appear consecutively, enabling a linear scan to detect overlaps.
Complexity
Sorting dominates the time complexity at O(n log n), which is acceptable for large inputs.
Iterate Through Intervals to Count and Resolve Overlaps
| 4 | res = 0
|
| 5 | prev_end = intervals[0][1]
|
| 7 | for start, end in intervals[1:]:
|
| 8 | if start >= prev_end:
|
| 9 | prev_end = end
|
| 10 | else:
|
| 11 | res += 1
|
| 12 | prev_end = min(end, prev_end)
|
Objective
To scan intervals and increment removal count when overlaps are detected, updating the tracking end time to maintain the earliest possible end.
Key Insight
When the current interval overlaps with the previous one (start < prev_end), removing the interval with the later end time preserves the earliest end boundary, maximizing space for future intervals. This greedy choice is the key to minimizing removals. Updating prev_end to the minimum end time ensures the algorithm always tracks the tightest boundary.
Interview Quick-Check
Core Logic
When intervals overlap, increment removal count and update prev_end to the smaller end time to keep the interval that allows more future intervals.
State & Boundaries
The loop starts from the second interval because the first interval is always included initially.
Common Pitfalls & Bugs
Failing to update prev_end to the minimum end time when removing an interval can cause incorrect overlap detection later.
Return the Total Number of Intervals Removed
| 14 | return res |
Objective
To output the minimum number of intervals that must be removed to eliminate all overlaps.
Key Insight
After processing all intervals, the removal count reflects the minimal removals needed because the algorithm greedily kept intervals with earliest end times, ensuring maximal non-overlapping intervals.
Interview Quick-Check
Core Logic
Returning the removal count completes the solution, representing the minimal removals required.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
prev_end = min(end, prev_end)Update prev_end to the minimum of current and previous ends to keep earliest finishing interval.
Updating prev_end to the minimum end time is the core greedy step that guarantees optimality by always keeping the interval that frees up the most room for subsequent intervals.
res += 1Increment removal count due to overlap.
Incrementing the removal count here is critical because it directly accounts for the minimal number of intervals that must be removed to resolve detected overlaps.
intervals.sort()Sort intervals by their start time in ascending order.
Sorting by start time arranges intervals so that any overlap can be detected by comparing consecutive intervals, enabling a linear scan to resolve conflicts efficiently.
if start >= prev_end:Check if current interval starts after or at the previous end time (no overlap).
If the current interval does not overlap with the previous, update prev_end to the current interval's end to continue tracking the boundary.
else:Handle the case where current interval overlaps with previous.
Detecting overlap triggers removal logic to maintain a non-overlapping set.
prev_end = intervals[0][1]Set prev_end to the end time of the first interval.
Tracking the end of the last included interval allows the algorithm to detect overlaps with subsequent intervals by comparing start times.
prev_end = endUpdate prev_end to current interval's end when no overlap occurs.
Updating prev_end to the current interval's end maintains the correct boundary for future overlap checks.
for start, end in intervals[1:]:Iterate over intervals starting from the second interval.
The first interval is always included initially, so iteration begins at the second to check for overlaps.
return resReturn the total count of removed intervals.
Returning the accumulated removal count provides the minimal number of intervals to remove to achieve a non-overlapping set.
res = 0Initialize removal count to zero.
This variable accumulates the number of intervals removed to achieve a non-overlapping set, forming the final output.
Test Your Understanding
Why does choosing to keep the interval with the earliest end time among overlapping intervals lead to an optimal solution?
Because keeping the interval that ends earliest leaves the maximum room for subsequent intervals to fit without overlapping, thereby maximizing the number of intervals kept and minimizing removals.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Non-overlapping Intervals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Non-overlapping Intervals drill