题解 | #合并区间#
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
2022.0902算法第51题合并区间
这题在写代码时遇到一下困难：
1、每两个区间进行比较，这样总会少一个区间，例如从第一个开始，则最后一个就可能遍历不到
这样想的思路是有问题的，因为需要比较的是结果区间的最后一个元素和给定区间依次比较，这样是不涉及数组问题。
2、在添加到结果数组时，如果连着三个都是需要合并的区间，那么怎么比？比较的对象就应该是结果数组中的最后一个区间
也就是结果数组的最后一个区间与给定的区间进行依次比较。
以上两个问题，没有想明白，导致写代码时总是出错，可以看出，以上两个问题出现的原因还是具体实施细节有问题
直到先排序，然后将能合并的区间进行合并，但是这个怎么合并就需要仔细思考了
还是有好多问题需要注意。现在在想觉着但是怎么就想不明白呢。。。（加练）
还有一点关于谓词的，需要使用静态函数才能充当谓词（函数指针），否则会报错。
//谓词，用于对区间排序，按左边界升序排列
//这里需要使用静态函数，要不设置为全局函数也行，应该是函数指针的问题
//静态函数指针和普通函数指针是不一样的
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;
}
