LeetCode 1288 Remove Covered Intervals
概述
https://leetcode.com/problems/remove-covered-intervals/
暴力遍历
排序的时候注意处理首元素相同的情况。
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
vector<bool> ok(intervals.size(), true);
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b)->bool {
if (a[0] == b[0]) return a[1] > b[1]; // ascend
else return a[0] < b[0]; // descend
});
for (int i = 0; i < intervals.size(); i ++) {
if (ok[i]) {
for (int j = i + 1; j < intervals.size(); j ++) {
if (intervals[j][0] >= intervals[i][1]) break;
if (intervals[j][1] <= intervals[i][1]) {
ok[j] = false;
}
}
}
}
int count = 0;
for (auto o : ok) count += o;
return count;
}
};
时间复杂度 O(n^2)。
O(n) 的解法
https://labuladong.gitee.io/algo/4/31/129/#区间覆盖问题
看 labuladong 的解法，貌似如果区间被合并区间覆盖也算？但是为啥我上面通过了嘞？
不管了。