无重叠区
按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。
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); // for(auto it:intervals) // cout<<'['<<it[0]<<','<<it[1]<<']'<<endl; 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; //总数减去非重叠的数，就是移除重叠的数 } };
二刷
class Solution { public: static bool cmp(vector<int> &a , vector<int> &b) { if(a[0] == b[0]) return a[1] < b[1]; else return a[0] < b[0]; } int eraseOverlapIntervals(vector<vector<int>>& intervals) { if(intervals.size() <=1) return 0; int result = 0; sort(intervals.begin(),intervals.end(),cmp); for(int i=1 ; i<intervals.size() ;i++) { if(intervals[i][0] < intervals[i-1][1]) { result++; intervals[i][1] = min(intervals[i][1],intervals[i-1][1]); } } return result; } };
