那个网站推作者百度首页优化排名

前言

题目：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];elsereturn 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;}
};

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