题目

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

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

解答 & 代码

区间问题的两个技巧：

排序：常见的排序方法就是按照区间起点排序，或者先按照起点升序排序，若起点相同，则按照终点降序排序。

本题就是先按照区间起点升序排序，若区间起点相同，则按照区间终点降序排序

画图：画出两个区间所有可能的相对位置，分情况讨论（下图的 case 2、3 可以合并，都是不能覆盖）

另，C++ sort 自定义排序规则的写法见下面代码：

class Solution {
private:
    // 自定义排序规则：按照区间起点升序排序，若区间起点相同，则按区间终点降序排序
    static bool cmp(vector<int> a, vector<int> b)
    {
        return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
    }
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        // 1. 排序：按照区间起点升序排序，若区间起点相同，则按区间终点降序排序
        sort(intervals.begin(), intervals.end(), cmp);

        int left = intervals[0][0];
        int right = intervals[0][1];
        int result = 0;        // 统计可以被覆盖的区间数
        for(int i = 1; i < intervals.size(); ++i)
        {
            vector<int> curInterval = intervals[i];
            // case1：如果当前区间被 [left, right] 覆盖，则 result 计数+1
            if(right >= curInterval[1])
                ++result;
            // case2 / 3：如果当前区间和 [left, right] 相交/无交集，则当前区间不能被覆盖
            // 用当前区间替换 [left, right]
            else if(right < curInterval[1])
            {
                left = curInterval[0];
                right = curInterval[1];
            }
        }
        // 原区间数 - 被覆盖的区间数，即剩余区间数
        return intervals.size() - result;
    }
};

复杂度分析：设有 N 个区间

时间复杂度 O(N log N)：排序的时间复杂度
空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：104 ms, 在所有 C++ 提交中击败了 10.54% 的用户
内存消耗：28.8 MB, 在所有 C++ 提交中击败了 4.99% 的用户

hot 100

[中等] 1288. 删除被覆盖区间

题目

解答 & 代码