leetcode 435 无重叠区间

超、凢脫俗 2022-09-15 05:51 137阅读 0赞

## 前言 ##

题目：[435. 无重叠区间][435.]

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

--------------------

## 提交代码 ##

### 方法一：起点排序 ###

之前做过[leetcode 452 用最少数量的箭引爆气球][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;
        }
    };

总的来说，方法二简单点，但是不容易想到。方法一在原来思维的基础上，稍加改变，便可以想到。

[435.]: https://leetcode-cn.com/problems/non-overlapping-intervals/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.md
[leetcode 452]: https://blog.csdn.net/sinat_38816924/article/details/120679824