Remove Covered Intervals
Problem
Given a list of intervals, return the number of intervals remaining after removing all intervals that are covered by another interval in the list. An interval [a,b) is covered by [c,d) if and only if c <= a and b <= d.
- 1 ≤ intervals.length ≤ 1000
- intervals[i].length == 2
- 0 ≤ start_i < end_i ≤ 10⁵
Example
intervals = [[1,4],[3,6],[2,8]]2First, sort intervals by start ascending and end descending: [[1,4],[2,8],[3,6]]. The interval [3,6] is covered by [2,8] because 2 <= 3 and 6 <= 8, so it is removed. The remaining intervals are [1,4] and [2,8], so the output is 2.
Approach
Straightforward Solution
A brute-force approach compares every interval against every other interval to check coverage, resulting in O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
An interval is covered if there exists another interval that starts at or before it and ends at or after it. Sorting intervals by start ascending and end descending ensures that any covered interval appears after its covering interval.
Path to Optimal
By sorting intervals by start ascending and end descending, the algorithm can scan once, tracking the maximum end seen so far. If the current interval's end is less than or equal to the maximum end, it is covered and skipped. Otherwise, it is counted and updates the maximum end. This reduces the problem to O(n log n) due to sorting and a single linear scan.
Optimal Approach
Sort intervals by start ascending and end descending. Initialize a counter for remaining intervals and a variable to track the maximum end seen. Iterate through intervals; if the current interval's end is greater than the maximum end, increment the counter and update the maximum end. Return the counter as the number of remaining intervals.
Time
O(n log n)
Sorting the intervals takes O(n log n) time. The subsequent single pass through the sorted list is O(n), so the overall time complexity is dominated by sorting.
Space
O(1)
The algorithm uses a constant amount of extra space for counters and variables, modifying the input list in place for sorting.
Pattern Spotlight
Greedy Algorithms (Interval Coverage via Sorting)
Sorting intervals by start ascending and end descending arranges intervals so that any covered interval follows its covering interval, enabling a single pass to identify and discard covered intervals by tracking the maximum end boundary.
Solution
| 1 | class Solution: |
| 2 | def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: |
| 3 | |
| 4 | intervals.sort(key=lambda x: (x[0], -x[1])) |
| 5 | |
| 6 | remaining = 0 |
| 7 | max_end = 0 |
| 8 | |
| 9 | for start, end in intervals: |
| 10 | if end > max_end: |
| 11 | remaining += 1 |
| 12 | max_end = end |
| 13 | |
| 14 | return remaining |
Step-by-Step Solution
Sort Intervals by Start Ascending and End Descending
| 4 | intervals.sort(key=lambda x: (x[0], -x[1])) |
Objective
To arrange intervals so that potential covering intervals come before covered intervals.
Key Insight
Sorting by start ascending ensures intervals are processed in order of their start points. Sorting by end descending for intervals with the same start places longer intervals first, guaranteeing that any interval that could cover another appears before it. This ordering is critical to enable a single linear scan to detect coverage efficiently.
Interview Quick-Check
Core Logic
Sorting intervals by (start ascending, end descending) arranges intervals so that any covering interval precedes the intervals it covers.
Common Pitfalls & Bugs
Sorting by end ascending instead of descending would place shorter intervals first, breaking the coverage detection logic.
Scan Intervals to Count Non-Covered Ones by Tracking Maximum End
| 6 | remaining = 0 |
| 7 | max_end = 0 |
| 9 | for start, end in intervals: |
| 10 | if end > max_end: |
| 11 | remaining += 1 |
| 12 | max_end = end |
Objective
To iterate through sorted intervals and count those not covered by previously seen intervals.
Key Insight
By maintaining the maximum end seen so far, the algorithm can determine if the current interval is covered: if its end is less than or equal to the maximum end, it is covered and skipped. Otherwise, it is counted and updates the maximum end. This greedy approach leverages the sorted order to avoid nested comparisons and achieve linear time scanning.
Interview Quick-Check
Core Logic
Track the maximum end of intervals seen so far; if the current interval's end is greater, it is not covered and increments the count.
State & Boundaries
Initialize max_end to 0 and remaining count to 0 before scanning.
Common Pitfalls & Bugs
Failing to update max_end when a new interval is counted leads to incorrect coverage detection.
Return the Count of Remaining Intervals
| 14 | return remaining |
Objective
To output the final number of intervals that are not covered by any other interval.
Key Insight
After scanning all intervals, the remaining count accurately reflects the number of intervals that are not covered. Returning this value completes the solution.
Interview Quick-Check
Core Logic
Return the count of intervals that were identified as not covered during the scan.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if end > max_end:Check if current interval's end is greater than max_end.
If the current interval extends beyond the maximum end seen, it cannot be covered by any previous interval and must be counted.
intervals.sort(key=lambda x: (x[0], -x[1]))Sort intervals by start ascending and end descending.
This sorting order ensures that intervals that could cover others appear first, enabling a single pass to detect coverage by comparing ends.
max_end = endUpdate max_end to current interval's end.
Updating max_end ensures that coverage detection for subsequent intervals is accurate, reflecting the furthest reach of intervals seen so far.
max_end = 0Initialize variable to track maximum end seen so far.
Tracking the maximum end allows the algorithm to detect if the current interval is covered by comparing its end to this value.
remaining += 1Increment count of remaining intervals.
Counting intervals that are not covered is the core output of the algorithm, directly contributing to the final answer.
return remainingReturn the count of intervals not covered.
Returning the accumulated count completes the solution, providing the number of intervals remaining after coverage removal.
for start, end in intervals:Iterate through each interval's start and end.
Processing intervals in sorted order is essential to apply the greedy coverage detection logic.
remaining = 0Initialize counter for remaining intervals.
This variable accumulates the count of intervals that are not covered by any previously seen interval.
Test Your Understanding
Why does sorting intervals by start ascending and end descending guarantee that covered intervals appear after their covering intervals?
Because intervals with the same start are ordered with longer intervals first (due to descending end), any interval that could cover another appears before it. This ordering ensures that when scanning, the maximum end seen so far corresponds to the covering interval, allowing detection of covered intervals by comparing ends.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Remove Covered Intervals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove Covered Intervals drill