贪心算法-找不重叠的区间段

1.说明

有N个区间片段，查找其中不重叠的片段最大个数。例如(6 8),（2 4）,（3 5）,（1 5）,（5 9）,(8 10)这6个片段中，不重叠的片段最大个数为3，分别为（2 4），(6 8)，(8 10)。

2.解析

先按照起始位置从小到大进行排序，使用贪心算法使有效片段尽可能小，即结束位置更靠前。当前片段如果属于上个有效片段的子段，则上个有效片段无效，被当前片段替代；当前片段如果和上个有效片段不重叠，则记作有效片段。
1.将N个片段按照起始位置从小到大进行排序，（1 5），（2 4），（3 5），（5 9），(6 8)，(8 10)。
2.按照上述判断方法遍历这N个片段，找出不重叠的有效字段，如下图所示，分别为"新1"、"新2"、"3"这三个片段。

3.代码实现

int findMostIntervals(vector<vector<int>> intervals, int n) 
{
    if(n==1)
        return 1;
int result=0;
sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int>b){
    return a[0]<b[0];//按照起始位置从小到大排序
});
int curStart,curEnd=0;
int preStart=intervals[0][0];
int preEnd=intervals[0][1];
result++;//先将第一个片段当作有效片段
auto it=intervals.begin();
for(++it;it!=intervals.end();++it)//从第二个片段开始遍历
{
    curStart=(*it)[0];
    curEnd=(*it)[1];
    //case1
    if(curStart>=preStart && curEnd<=preEnd)
    {
        //巧:更新绝对不可能更坏的结果，因为新的片段结束位置更小
        preStart=curStart;
        preEnd=curEnd;
    }
    //case 2
    else if(curStart>=preEnd) //新的有效片段
    {
        result++;
        preStart=curStart;
        preEnd=curEnd;
    }
}
return result;

}