Remove Covered Intervals
Given a list of intervals
, remove all intervals that are covered by another interval in the list.
Interval [a,b)
is covered by interval [c,d)
if and only if c <= a
and b <= d
.
After doing so, 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
Example 3:
Input: intervals = [[0,10],[5,12]]
Output: 2
Example 4:
Input: intervals = [[3,10],[4,10],[5,11]]
Output: 2
Example 5:
Input: intervals = [[1,2],[1,4],[3,4]]
Output: 1
Constraints:
1 <= intervals.length <= 1000
intervals[i].length == 2
0 <= intervals[i][0] < intervals[i][1] <= 10^5
All the intervals are unique.
Solutions
🧠 Cpp
class Solution
{
enum {START, END};
public:
//O(n log n) solution: sort + 1 pass
int removeCoveredIntervals(vector<vector<int>>& intervals)
{
std::sort(begin(intervals), end(intervals),
[](auto a, auto b)
{
return a[END] == b[END] ? a[START] > b[START] : a[END] < b[END];
}
);
//copy data to list for O(1) erasure
std::list<vector<int>> i_vals(begin(intervals), end(intervals));
//ENDs is already sorted, so next element has end >= than prev
//only thing is to check the start of the interval, if prev has START > next start
//then it's covered
for(auto iter = begin(i_vals); iter != prev(end(i_vals));)
{
if((*iter)[START] >= (*next(iter))[START])
{
iter = i_vals.erase(iter);
if(iter != begin(i_vals))
advance(iter, -1);
}
else
++iter;
}
return i_vals.size();
}
};
Last updated
Was this helpful?