leetcode 435 无重叠区间-蒲公英云

leetcode 435 无重叠区间

前言

题目：435. 无重叠区间

参考题解：无重叠区间-代码随想录

提交代码

方法一：起点排序

之前做过leetcode 452 用最少数量的箭引爆气球，我们很自然想到，将所有的区间按照起点进行排序。

之后，需要找到移除区间的最小数量，使剩余区间互不重叠。

贪心思路：当已排序的两个区间重叠时，必然要删除一个。删除区间终点较大的区间，可以为后面区间腾出空间，以保证移除最少区间。

class Solution {
public:
    struct cmp{
        bool operator() (vector<int>& v1, vector<int>& v2){
            // 第一个元素越小越靠前；第一个元素相等，第二个元素越大越靠前，保证屁股越长，越容易被删除
            if(v1[0]<v2[0])
                return true;
            else if(v1[0]==v2[0])
                return v1[1]>v2[1];
            else
                return false;
        }
    };
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0 || intervals.size()==1)
            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++;
                end = min(end,intervals[i][1]); // 保留屁股较短的那个==删除屁股较长的那个
                continue;
            }
            end = intervals[i][1]; // 使用最新的一个屁股作为end
        }
        return count;
    }
};

方法二：终点排序

下面思路和代码来自参考题解。

贪心思路：使用每个区间的终点进行排序。每次取非交叉区间的时候，都是可右边界最小的来做分割点（这样留给下一个区间的空间就越大）

这个方法不太容易想到。

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;
    }
};