题目 1288. 删除被覆盖区间

难度 中等

>给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [ [1,4], [3,6], [2,8] ] 输出：2 解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

提示：

1 <= intervals.length <= 1000 0 <= intervals[i][0] < intervals[i][1] <= 10^5 对于所有的 i != j：intervals[i] != intervals[j]

解法1 - 枚举

看到这题目第一眼，我的思路就是两次循环遍历，枚举所有区间来比较，然后判断是否被覆盖，是的话总数减一。 要注意的就是，确定该区间被覆盖了之后就可以跳过了 这个思路很容易想到，但是耗时比较高

复杂度分析：

时间复杂度：O(N^2)，其中 N 是区间的个数 空间复杂度：O(1)

class Solution {
          
   
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
          
   
    int count = intervals.size();
    for(int i = 0; i < intervals.size(); i++){
          
   
        for(int j = 0; j < intervals.size(); j++){
          
   
            if( i!=j && intervals[j][0] <= intervals[i][0] && intervals[j][1] >= intervals[i][1]){
          
   
                count --;
                break;
            }
        }
    }
        return count;
    }
};

解法2 - 排序+遍历

复杂度分析：

时间复杂度：O( N*logN )，其中 N 是区间的个数 空间复杂度：O( logN )，为排序需要的空间

这里给出官方的解题思路。 先假设所有区间的左端点都不同（先不考虑相同的情况），将所有区间按照左端点递增进行排序，那么排完后 对于列表中第 i 个区间A [ li,ri ）：

出现在其之前的任一区间 B[ lj, rj），都满足 lj < li，因此只要再满足一个条件：即 rj >= ri，那么区间 A一定会被区间 B 覆盖，也就是说，只要出现在 A 之前的某一区间的右端点的最大值 rmax = max（r1,r2…ri-1），满足 rmax >= ri，那么 A 一定会被覆盖。 然后考虑左端点相同的情况，如果只按照区间左端点递增排序，那么对于出现在区间 A 后面的某个区间还是有可能将其覆盖（即左端点相同，右端点大于 A 的区间）。解决方法：将左端点作为第一关键字递增、右端点作为第二关键字递减进行排序，这样，区间 A 就不可能被任何出现在其之后的区间覆盖了。

class Solution {
          
   
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
          
   
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {
          
   
            return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
        });
        int ans = n;
        int rmax = intervals[0][1];
        for (int i = 1; i < n; ++i) {
          
   
            if (intervals[i][1] <= rmax) {
          
   
                --ans;
            }
            else {
          
   
                rmax = max(rmax, intervals[i][1]);
            }
        }
        return ans;
    }
};