Leetcode每日一题 —— 1288. 删除被覆盖区间

排序后顺序找到被覆盖的区间，我写得还麻烦了一点，因为我在起始点相同时也对结束点升序排列了，这样就还要多一个后面区间能覆盖前面区间的判断。

像佬友这样对结束点降序排列就可以免去这多一步的判断了。

class Solution {

public:

    int removeCoveredIntervals(vector<vector<int>>& intervals) {

        // 按区间起始点进行排序

        sort(intervals.begin(),intervals.end(),[&](const vector<int>& a,const vector<int>& b){

            if(a[0]==b[0]){

                return a[1]<b[1];

            }

            return a[0]<b[0];

        });

        int prevStart=-1,prevEnd=-1;

        int res=intervals.size();

        for(auto& itv:intervals){

            if(itv[0]>=prevStart&&itv[1]<=prevEnd){

                res--;

            }else if(prevStart>=itv[0]&&prevEnd<=itv[1]){

                // 可能后一个区间覆盖掉前一个区间，比如 [1,2], [1,4]

                res--;

                prevStart=itv[0];

                prevEnd=itv[1];

            }else{

                prevStart=itv[0];

                prevEnd=itv[1];

            }

        }

        return res;

    }

};

class Solution:

    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:

        intervals.sort(key=lambda x: (x[0], -x[1]))

        r = ans = 0

        for x, y in intervals:

            if y > r:

                ans += 1

                r = y

        return ans

算术评级: 5 第 15 场双周赛 Q2 难度分 1375

丑陋的解法，纯模拟

class Solution:

    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:

        intervals.sort(key=lambda x:x[1]-x[0],reverse=True)

        

        cur_intervals = []

        for a, b in intervals:

            n = len(cur_intervals)

            idx = 0

            flag = True

            while idx<n:

                cur_a, cur_b = cur_intervals[idx]

                if cur_a<=a<b<=cur_b:

                    flag=False

                    break

                idx+=1

            if flag:

                cur_intervals.append([a,b])

        return len(cur_intervals)

丑陋了。

class Solution {

public:

    int removeCoveredIntervals(vector<vector<int>>& intervals) {

        std::sort(intervals.begin(),intervals.end(),[](const auto& a, const auto& b) -> bool {

            if(a[0] != b[0]) {

                return a[0] < b[0];

            } else {

                return a[1] > b[1];

            }

        });

        priority_queue<int,vector<int>,greater<int>> q;

        int lastr = -1;

        int res = intervals.size();

        for(const auto& inter : intervals) {

            int l = inter[0], r = inter[1];

            if(r > lastr) {

                while(!q.empty() && q.top() < l) {

                    q.pop();

                }

                q.push(r);

                lastr = r;

            } else {

                res--;

            }

        }

        return res;

    }

};

好久没写了…

impl Solution {

    pub fn remove_covered_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {

        intervals.sort_by(|a, b| a[0].cmp(&b[0]).then(b[1].cmp(&a[1])));

        let mut ans = 0i32;

        let mut tmp = &intervals[0];

        for interval in intervals[1..].iter() {

            if tmp[0] <= interval[0] && tmp[1] >= interval[1] {

                ans += 1;

            } else {

                tmp = &interval;

            }

        }

        intervals.len() as i32 - ans

    }

}

对左端点排序，可以保持 l_{i-1} < l_i，遍历维护最远右端点 mxr ，如果当前区间 r_i < mxr, 则满足

被覆盖

class Solution {

public:

    int removeCoveredIntervals(vector<vector<int>>& intervals) {

        int n = intervals.size();

        sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b){

            if (a[0] == b[0]) return a[1] > b[1];

            return a[0] < b[0];

        });

        int ans = n;

        for (int i = 1, mxr = intervals[0][1]; i < n; i++) {

            if (intervals[i][1] <= mxr) {

                ans--;

            } else {

                mxr = max(mxr, intervals[i][1]);

            }

        }

        return ans;

    }

};