题目描述

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

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

算法

(排序) $O(n \log n)$

1. 我们将区间按照左端点从小到大排序，左端点相同的，按照右端点从大到小排序。
2. 排序后，线性遍历整个区间，设置一个当前右端点 r，如果遍历过程中，发现当前区间的右端点小于等于 r，则说明这个区间被覆盖了。否则，更新 r 为当前区间的右端点。

时间复杂度

• 排序后遍历一次数组，故时间复杂度为 $O(n \log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        auto cmp = [](const vector<int>& x, const vector<int>& y) {
            if (x[0] != y[0])
                return x[0] < y[0];
            return x[1] > y[1];
        };

        sort(intervals.begin(), intervals.end(), cmp);

        int r = -1;
        int ans = n;
        for (int i = 0; i < n; i++)
            if (intervals[i][1] <= r) {
                ans--;
            } else {
                r = intervals[i][1];
            }

        return ans;
    }
};