Remove Covered Intervals
MedPrompt
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 <= 105- All the given intervals are unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves comparing every interval with every other interval in the list. For each interval, we check if it is 'covered' by any other interval according to the given definition.
Algorithm
- Initialize a boolean array
removedof sizen(number of intervals) to allfalse. - Iterate through the intervals with an index
ifrom0ton-1. - For each interval
i, iterate through the intervals with an indexjfrom0ton-1. - If
iis the same asj, skip the comparison. - Check if interval
i([a, b)) is covered by intervalj([c, d)) using the conditionc <= aandb <= d. - If interval
iis covered, setremoved[i] = trueand break the inner loop. - After the loops, count the number of
falseentries in theremovedarray. This count is the result.
Walkthrough
We can solve this problem by iterating through each interval and then, in a nested loop, comparing it against every other interval.
We use a boolean array, removed, of the same size as the input intervals array, to keep track of which intervals have been found to be covered.
The outer loop selects an interval i, and the inner loop selects another interval j.
Inside the inner loop, we check if interval i is covered by interval j. The condition for an interval [a, b) to be covered by [c, d) is c <= a and b <= d.
If interval i is covered by j, we mark removed[i] as true and can break the inner loop for the current i, since we only need to find one interval that covers it.
After the loops complete, we count the number of false values in the removed array, which corresponds to the number of remaining, non-covered intervals. Alternatively, we can count the true values and subtract from the total number of intervals.
class Solution { public int removeCoveredIntervals(int[][] intervals) { int n = intervals.length; boolean[] removed = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { continue; } // Check if interval i is covered by interval j // interval i = [intervals[i][0], intervals[i][1]) // interval j = [intervals[j][0], intervals[j][1]) if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) { removed[i] = true; break; // Found a covering interval, move to the next i } } } int remainingCount = 0; for (int i = 0; i < n; i++) { if (!removed[i]) { remainingCount++; } } return remainingCount; }}Complexity
Time
O(N^2), where N is the number of intervals. The nested loops lead to a quadratic time complexity as each interval is compared with every other interval.
Space
O(N) to store the `removed` boolean array.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large inputs due to the quadratic time complexity.
Solutions
Solution
class Solution { public int removeCoveredIntervals ( int [][] intervals ) { Arrays . sort ( intervals , ( a , b ) -> a [ 0 ] - b [ 0 ] == 0 ? b [ 1 ] - a [ 1 ] : a [ 0 ] - b [ 0 ]); int [] pre = intervals [ 0 ]; int cnt = 1 ; for ( int i = 1 ; i < intervals . length ; ++ i ) { if ( pre [ 1 ] < intervals [ i ][ 1 ]) { ++ cnt ; pre = intervals [ i ]; } } return cnt ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.