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.
这道题给了我们一个区间数组，说是让移除所有被完全包含的区间，比如区间 [3, 6] 就是完全包含在区间 [2, 8] 中的，注意这里完全相同的两个区间也可以算是包含关系。当然最简单粗暴的方法就是对于每个区间，都遍历其他所有的区间，看是否包含或者被包含，但这种方法太不高效，估计过不了 OJ，所以博主试都没试。得想一想有没有什么简便的方法，由于一个区间要被另一个区间包含，那么小区间的左边界要大一些，右边界要小一些，所以如果按左边界排序，则后面的区间更容易被前面的区间包含。排序后的数组，当前区间的左边界一定是不小于前面区间的左边界的，所以只要比较右边界，若当前区间的右边界小于等于前面任意一个区间的右边界的话，则当前的区间一定是被包括的，所以需要统计前面区间中的最大右边界。被包括的区间就不用计数了，那么反过来，不被包括的时候，res 就要自增1。若当前区间的右边界大于前面区间的最大右边界，且当前区间的左边界大于之前最大右边界区间的左边界时，当前区间不会包括或被包括于任何区间，此时 res 要自增1，而且 left 要更新为当前的左边界，每次遍历完一个区间后，都用该区间的右边界来更新 right 即可，参见代码如下：
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int res = 1, n = intervals.size(), left = intervals[0][0], right = intervals[0][1];
for (int i = 1; i < n; ++i) {
if (intervals[i][0] > left && intervals[i][1] > right) {
left = intervals[i][0];
++res;
}
right = max(right, intervals[i][1]);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1288
参考资料：
https://leetcode.com/problems/remove-covered-intervals/
LeetCode All in One 题目讲解汇总(持续更新中…)
喜欢请点赞，疼爱请打赏❤️.
微信打赏
|
Venmo 打赏
—|—
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
