LC435无重叠子区间

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。 示例 2: 输入: [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。 示例 3: 输入: [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

题目解答

本题主要考察的为贪心算法。大致思路为每次都需要选取右端点尽可能小的区间，因为这样，才可以让后续的区间有更大的选择的余地。所以需要用到排序，在这里记录的话主要是为了学习一下双重嵌套vector如何排序使用，我排序的规则大概是，首先升序排右端点，如果右端点相同的话，则按照左端点升序的思路。在这里记录一下我的排序的方法。代码如下：

bool cmp(vector<int> &a,vector<int> &b){ return a[1]<b[1]||(a[1]==b[1]&&a[0]<b[0]) //这里是自己需要记住的地方 } int eraseOverlapIntervals(vector<vector<int>>& intervals) { if(intervals.size()==0){ return 0; } sort(intervals.begin(),intervals.end(),cmp); int cnt = 0; int left = intervals[0][0]; int right = intervals[0][1]; for(int i = 1 ; i < intervals.size() ; i++ ){ if(intervals[i][0]>= right){ left = intervals[i][0]; right = intervals[i][1]; }else{ cnt++; } } return cnt; }