题目描述

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

只有当 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

还是逐个比较各个区间 只是被包含的区间直接填充不可能数字 避免进行数组删减移动 浪费时间

C++ 代码

class Solution {
public:

    bool Check( vector<vector<int>>&  v,int a,int b){
        if(v[a][0] == -1 || v[a][1] == -1 || v[b][0]==-1 || v[b][1] == -1){
            return false;
        }

        if(v[a][0] <= v[b][0] && v[b][1] <= v[a][1]){
            //a 覆盖b
            v[b][0] = -1; v[b][1] = -1;
            return true;
        }

        return false;
    }

    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        int count = 0;
        for(int i = 0; i < intervals.size()-1;i++){
            for(int j =i+1;j <intervals.size();j++){
                if(Check(intervals,i,j)){
                    count++;                       
                }else if(Check(intervals,j,i)){
                    count++;
                    //当前的选择已经优化掉了直接break
                    break;
                }
            }            
        }

        return intervals.size()-count;
    }
};

速度稍微有点慢

//===========================================================================================

网友 mxyzptlk13 提出排序预处理 可提高速度
leetcode 测速有点迷 20-48ms四处跳动 但是对于后面的$n^2$比较有加速是肯定的
代码如下

class Solution {
public:

    static bool cmp(const vector<int>& a, const vector<int>& b)
{
    if (a[0] > b[0])
        return true;
    if (a[0] == b[0] && a[1] <= b[1])
        return true;
    return false;
}
int removeCoveredIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    int count = 0;
    sort(intervals.begin(), intervals.end(), cmp);

    for (int i = 0; i < intervals.size(); i++) {
        for (int j = i + 1; j < intervals.size(); j++) {
            if ( intervals[i][0] >= intervals[j][0] && intervals[i][1] <= intervals[j][1]) {
                count++;
                break;
            }
            else  if(intervals[i][0] < intervals[j][0]) {
                break;
            }
        }
    }

    return intervals.size()-count;
}

};