力扣 435. 无重叠区间-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 435. 无重叠区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源：https://leetcode.cn/problems/non-overlapping-intervals/description/

力扣 435. 无重叠区间,开始C++吧,leetcode,算法,c++,贪心算法

力扣 435. 无重叠区间,开始C++吧,leetcode,算法,c++,贪心算法 C++题解1：对区间进行排序，根据区间的末端进行排序，小的在前，大的在后；由于有重复区间，我们拿后面的区间去看是否跟前面的区间重合，如果后面区间的前端大于前面区间的后端，则说明重合；但在排序会遇到末端平齐的，哪个在前呢？当然是前端更小的在前，因为前端更小就说明它更长，在与前面的区间比较时，可以把它跳过（res++）。

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

C++题解2（来源代码随想录）：根据右区间进行排序，找到不交叉的区间，用总数减去不交叉的区间得到去重数。

class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};

C++题解3（来源代码随想录）：根据左区间进行排序，直接计算重复区间。文章来源地址https://www.toymoban.com/news/detail-607695.html

class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 改为左边界排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0; // 注意这里从0开始，因为是记录重叠区间
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {   
            if (intervals[i][0] >= end)  end = intervals[i][1]; // 无重叠的情况
            else { // 重叠情况 
                end = min(end, intervals[i][1]);
                count++;
            }
        }
        return count;
    }
};

到了这里，关于力扣 435. 无重叠区间的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！