1288. Remove Covered Intervals

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 <= 1000
  • intervals[i].length == 2
  • 0 <= 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/

https://leetcode.com/problems/remove-covered-intervals/discuss/451277/JavaC%2B%2BPython-Sort-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation