题解 | #合并区间#

//谓词，用于对区间排序，按左边界升序排列
//这里需要使用静态函数，要不设置为全局函数也行，应该是函数指针的问题
//静态函数指针和普通函数指针是不一样的
static bool isG(const Interval &v1,const Interval &v2){
    return v1.start<v2.start;
}
vector<Interval> merge(vector<Interval> &intervals) {
    //定义结果数组
    vector<Interval> res;
    //如果没有区间，或者只有一个区间，则直接返回
    if(intervals.size()<=1)
        return intervals;
    //对区间进行排序，按左边界升序排列
    sort(intervals.begin(),intervals.end(),isG);
    //首先将第一个加入结果数组，这里感觉和动态规划相似
    res.push_back(intervals[0]);
    //进行遍历区间，每次是结果数组中的最后一个区间和当前区间作比较
    for(int i=1;i<intervals.size();i++){
        //结果数组中的最后一个区间的右边界和当前区间左边界作比较
        //如果左边界小于等于右边界，那么能够合并区间
        //将结果数组里的右边界更新为两个边界中较大的值。
        if(intervals[i].start<=res.back().end){
            //res.pop_back();
            res.back().end= max(res.back().end,intervals[i].end);
        }
        //否则，不能合并区间，则直接加入到结果数组
        else
            res.push_back(intervals[i]);
    }
    //返回结果
    return res;
}