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 <= 105First, 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) for comparing each interval with every other one.
Space Complexity: O(n) for the boolean array tracking covered intervals.
| 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. |
Remove Covered Intervals - Leetcode 1288 - Python • NeetCode • 15,239 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