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.
A more efficient approach is to first sort the intervals. By sorting them in a specific way, we can determine if an interval is covered in a single pass. We sort the intervals primarily by their start points in ascending order. If two intervals have the same start point, we sort them by their end points in descending order.
Algorithm
- Sort the
intervalsarray. The primary sorting key is the start point (ascending), and the secondary key is the end point (descending). - Initialize a counter
countto0and a variablemaxEndto0. - Iterate through the sorted intervals
[start, end]. - For each interval, check if its
endis greater thanmaxEnd. - If
end > maxEnd, it means this interval is not covered by any previous one. Incrementcountand updatemaxEnd = end. - If
end <= maxEnd, the interval is covered, so we do nothing. - Return
countafter the loop finishes.
Walkthrough
The key insight is that after sorting, we can process the intervals in a way that simplifies the check for covered intervals.
The sorting criteria are:
- Sort by the start point in ascending order.
- If start points are equal, sort by the end point in descending order.
This sorting strategy ensures that if we are at an interval i, any subsequent interval j cannot cover i. This is because either intervals[j][0] > intervals[i][0], or if intervals[j][0] == intervals[i][0], then intervals[j][1] <= intervals[i][1]. In neither case can j cover i.
Therefore, an interval can only be covered by an interval that appeared before it in the sorted list.
We can iterate through the sorted intervals and keep track of the maximum end point (maxEnd) seen so far.
An interval [start, end] is covered if its end point end is less than or equal to maxEnd. If end > maxEnd, the interval is not covered by any previous one, so we count it and update maxEnd to this new, larger end point.
import java.util.Arrays; class Solution { public int removeCoveredIntervals(int[][] intervals) { // Sort by start point ascending. If start points are equal, // sort by end point descending. Arrays.sort(intervals, (a, b) -> { if (a[0] != b[0]) { return a[0] - b[0]; } else { return b[1] - a[1]; } }); int count = 0; int maxEnd = 0; for (int[] interval : intervals) { // If the current interval extends beyond the max end point seen so far, // it is not covered. if (interval[1] > maxEnd) { count++; // This is a new, non-covered interval. maxEnd = interval[1]; // Update the max end point. } // Otherwise, the interval is covered by a previous one, so we ignore it. } return count; }}Complexity
Time
O(N log N), where N is the number of intervals. The dominant operation is sorting the array.
Space
O(log N) or O(N), depending on the space complexity of the sorting algorithm used. In Java, `Arrays.sort` for objects uses Timsort, which can take up to O(N) space in the worst case.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
The logic is elegant once the sorting strategy is understood.
Cons
Requires modifying the input array by sorting it, or using extra space to store a sorted copy.
The sorting logic (especially the secondary sort key) is crucial and might not be immediately obvious.
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 ; } }/** * @param {number[][]} intervals * @return {number} */ var removeCoveredIntervals = function (intervals) { intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])); let ans = 0; let pre = -Infinity; for (const [_, cur] of intervals) { if (cur > pre) { ++ans; pre = cur; } } return ans; };class Solution { public: int removeCoveredIntervals ( vector < vector < int >>& intervals ) { sort ( intervals . begin (), intervals . end (), []( const vector < int >& a , const vector < int >& b ) { return a [ 0 ] == b [ 0 ] ? b [ 1 ] < a [ 1 ] : a [ 0 ] < b [ 0 ]; }); int cnt = 1 ; vector < int > pre = intervals [ 0 ]; for ( int i = 1 ; i < intervals . size (); ++ i ) { if ( pre [ 1 ] < intervals [ i ][ 1 ]) { ++ cnt ; pre = intervals [ i ]; } } return cnt ; } };class Solution : def removeCoveredIntervals ( self , intervals : List [ List [ int ]]) -> int : intervals . sort ( key = lambda x : ( x [ 0 ], - x [ 1 ])) cnt , pre = 1 , intervals [ 0 ] for e in intervals [ 1 :]: if pre [ 1 ] < e [ 1 ]: cnt += 1 pre = e return cntVideo 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.