leetCode 435 无重叠区间（区间问题）

题目链接：点击查看

题目描述：

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

输入输出：

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

题目分析：

此题采取贪心策略 ，区间的结尾越小，预留给其他空间的结尾就越大，保留的空间也就越多， 具体方法 为把区间按照结尾的大小进行升序排序（在此用了c++的lambda匿名函数作为自定义排序方式 作为sort第三个参数），每次选择结尾小且和前一个选择的区间不重叠的区间。因此贪心策略为：优先保留结尾小且不相交的区间。

代码：

int eraseOverlapIntervals(vector<vector<int>>& intervals) 
{
     if(intervals.empty())
	 {
	   return 0;	
	 } 
	 int n=intervals.size();
	 sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int>b){
	    return a[1]<b[1];
	 });//用c++lambda匿名函数来自定义排序方式：即按照每个一维数组第二个元素大小升序排序 
	 int total=0,prev=intervals[0][1];//total表示所要移除区间的个数 
	 for(int i=1;i<n;i++)
	 {
	 	if(intervals[i][0]<prev)
	 	{
	 		++total;
		}
		else
	    {
	    	prev=intervals[i][1];
		}
	 }
     return total;	 
}