求合并后剩余区间个数

算法1

(排序 合并) $O(nlogn)$

C++ 代码

int removeCoveredIntervals(vector<vector<int>>& A) {
        int res = 0, left = -1, right = -1;
        sort(A.begin(), A.end());
        for (auto& v: A) {
            if (v[0] > left && v[1] > right) {
                left = v[0];
                ++res;
            }
            right = max(right, v[1]);
        }
        return res;
    }

很像基础课里的第一章最后一节：区间合并
区别就是LC已经帮你读好INPUT了。

sort left ascending and right decending
[[1,5],[1,4],[1,3],[1,2]]
Python代码

def removeCoveredIntervals(self, A):
        res = right = 0
        A.sort(key=lambda a: (a[0], -a[1]))
        for i, j in A:
            res += j > right
            right = max(right, j)
        return res