题解 | #合并区间#

合并区间

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;
}




#算法题#
全部评论

相关推荐

那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 15:58
投个小米提前批试试水,先投一个岗位看看形势,不行就再沉淀一下投第二个岗位,莫辜负
Java抽象带篮子:我嘞个骚刚,已经开始研发6g了吗
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务