1 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
2
3 注意:
4
5 可以认为区间的终点总是大于它的起点。
6 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
7 示例 1:
8
9 输入: [ [1,2], [2,3], [3,4], [1,3] ]
10
11 输出: 1
12
13 解释: 移除 [1,3] 后，剩下的区间没有重叠。
14 示例 2:
15
16 输入: [ [1,2], [1,2], [1,2] ]
17
18 输出: 2
19
20 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
21 示例 3:
22
23 输入: [ [1,2], [2,3] ]
24
25 输出: 0
26
27 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
28
29 来源：力扣（LeetCode）
30 链接：https://leetcode-cn.com/problems/non-overlapping-intervals
31 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
贪心算法策略。要达到目的就要优先保留结尾小且不相交的区间，因为这样才能保证余留给其他区间的空间更大，能够保留更多区间。为此我们先将数组按区间尾升序排列，以最小的区间尾为起点，每次与后一个的区间头相比，如果后一个的区间头小于上一个的区间尾则证明两个区间存在重叠，舍弃该区间，否则保留，并以当前新区间尾与后一个区间头进行比较，依次进行。
特别要提的是本题题解并不完美，仅为练习贪心算法做下记录。
实现代码：
1 class Solution {
2 public:
3 int eraseOverlapIntervals(vector<vector<int>>& intervals) {
4 if(intervals.empty())
5 return 0;
6 //先将区间数组按区间尾升序排序
7 sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int>b){return a[1]<b[1];});
8 int total = 0;int pre = intervals[0][1];
9 for(int i = 1;i<intervals.size();++i)
10 {
11 if(intervals[i][0]<pre)
12 total++;
13 else
14 pre = intervals[i][1];
15 }
16 return total;
17 }
18 };
原文：https://www.cnblogs.com/pionice/p/13354310.html