Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
Return the number of remaining intervals.
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
Example 2:
Input: intervals = [[1,4],[2,3]] Output: 1
Constraints:
1 <= intervals.length <= 1000intervals[i].length == 20 <= li < ri <= 105Problem Overview: You are given a list of intervals where each interval is represented as [start, end]. An interval is considered covered if another interval fully contains it. The task is to remove all covered intervals and return the number of remaining intervals.
Approach 1: Graph-Based Comparison (Implicit Graph) (O(n²) time, O(1) extra space)
Treat every interval as a node and check coverage relationships between all pairs. For each interval i, iterate through every other interval j. If j.start ≤ i.start and j.end ≥ i.end, interval i is covered and should not be counted. This brute-force comparison effectively builds an implicit coverage graph without storing edges. The method is straightforward and helps you reason about the definition of coverage, but the nested iteration leads to O(n²) time complexity. Space stays O(1) because only counters and temporary variables are used.
Approach 2: Sort by Start, End Descending (O(n log n) time, O(1) space)
The optimal solution relies on sorting. Sort intervals by start in ascending order. When two intervals share the same start, sort by end in descending order. This ordering guarantees that larger covering intervals appear before the smaller ones they might contain.
After sorting, scan the array once while tracking the maximum end value seen so far. If the current interval's end is less than or equal to that maximum, it is covered by a previous interval. Otherwise, it is a valid interval that should be counted, and the maximum end gets updated. Because sorting groups potential coverings together, a single linear pass is enough to detect coverage relationships.
This approach combines array traversal with sorting order to eliminate the need for pairwise comparisons. Sorting costs O(n log n), and the scan is O(n). No additional data structures are required beyond a few variables, so extra space remains O(1) (ignoring sort implementation details).
Recommended for interviews: The sorting approach is the expected solution. It shows you recognize that ordering intervals can simplify containment checks and reduce the complexity from O(n²) to O(n log n). Explaining the brute-force comparison first demonstrates clear understanding of the coverage rule, while the optimized sorting strategy shows strong algorithmic thinking using sorting and interval scanning patterns.
First, sort the intervals by their starting point. If two intervals have the same start, sort them by their ending point in descending order. This helps in ensuring that when you iterate, you can simply keep a check on the maximum end encountered and compare each interval to determine if it is covered.
This C solution includes sorting the 2D array of intervals based on custom rules as mentioned. After sorting, it iterates through each interval, and incrementally counts those that are not covered by keeping a check on the last maximum end encountered.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
Conceptually, treat each pair of intervals as a directed edge if one interval is covering another. Such implicit graph construction helps identify covered intervals. You process over this graph to recognize unique intervals not covered by others. This approach may be non-trivial compared to the sorting technique, but it provides a different perspective.
This C implementation checks each interval against every other to see if it is covered (acting as a graph edge implies coverage). An array tracks covered intervals, and the count reduces with each uncovered detection.
Time Complexity: O(n^2) for comparing each interval with every other one.
Space Complexity: O(n) for the boolean array tracking covered intervals.
We can sort the intervals in ascending order by their left endpoints, and if the left endpoints are the same, sort them in descending order by their right endpoints.
After sorting, we can traverse the intervals. If the right endpoint of the current interval is greater than the previous right endpoint, it means the current interval is not covered, and we increment the answer by one.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Sorting by Start and then by End Descending | Time Complexity: O(n log n) due to sorting. |
| Graph-Based Approach (Implicit Graph) | Time Complexity: O(n^2) for comparing each interval with every other one. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph-Based Comparison (Implicit Graph) | O(n²) | O(1) | Useful for understanding the coverage definition or when constraints are very small. |
| Sort by Start, End Descending | O(n log n) | O(1) | Optimal general solution. Preferred in interviews and large input sizes. |
Remove Covered Intervals - Leetcode 1288 - Python • NeetCode • 16,124 views views
Watch 9 more video solutions →Practice Remove Covered Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor