LeetCode 1288 Remove Covered Intervals

Tag: 区间问题 LeetCode Posted on 2022-03-01 16:55:57 Edited on 2022-03-01 17:07:05 Views: 154

概述

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 的解法,貌似如果区间被合并区间覆盖也算?但是为啥我上面通过了嘞?

不管了。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/