Leetcode|中等|区间贪心|435. 无重叠区间

SL_World

发布于 2021-09-18 08:38:27

46700

代码可运行

文章被收录于专栏：XX

运行总次数：0

代码可运行

1 区间终点贪心

没啥好说的，贪心算法中最简单的题，《算法设计与分析》教科书中贪心章节的第一道典例

class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < end) 
                count++;
            else end = intervals[i][1];
        }
        return count;
    }
};