题解 | #合并区间#

合并区间

http://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a

一.题目描述
NC37合并区间:
题目链接:https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6atpId=196&&tqId=37071&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一组区间,请合并所有重叠的区间,请保证合并后的区间按区间起点升序排列。
二.算法(贪心)
图片说明
1、将每个区间按左端点从小到大进行排序
2、如图所示,可分3种情况
情况一:当前区间完全被上一区间覆盖,直接跳过
情况二:将当前区间的右端点更新为上一区间的右端点,达到区间延长的效果
情况三:当前区间的左端点严格大于上一区间的右端点,则表示该区间不能合并,更新区间
下面是代码:

#include<algorithm>
bool cmp(Interval a,Interval b){//sort的比较函数
     if(a.start==b.start){
         return a.end<b.end;     
     }
    return a.start<b.start;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> q;
        sort(intervals.begin(), intervals.end(),cmp);
        int len=intervals.size();
        if(len==0) return intervals;
        for(int i=1;i<len;i++){
            if(intervals[i].start <= intervals[i-1].end){
                    //区间的合并
                    intervals[i].start = min(intervals[i-1].start,intervals[i].start);
                    intervals[i].end = max(intervals[i-1].end,intervals[i].end);
                } else{
                    //将合并好的区间放入
                     q.push_back(intervals[i-1]);
                }
        }
        q.push_back(intervals[len-1]);//最后一个区间放入
        return q;
    }
};

时间复杂度:O(n) 只需要进行排序后对所有区间进行一次遍历
空间复杂度:O(n) 需要额外开辟空间
优缺点:写起来简单,容易实现
三.算法(排序)
我们用数组ans存储最终的答案。首先,我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中,并按顺序依次考虑之后的每个区间:如果当前区间的左端点在数组ans中最后一个区间的右端点之后,那么它们不会重合,我们可以直接将这个区间加入数组ans的末尾;否则,它们重合,我们需要用当前区间的右端点更新数组ans中最后一个区间的右端点,将其置为二者的较大值。

#include<algorithm>
bool cmp(Interval a,Interval b){//sort的比较函数
     if(a.start==b.start){
         return a.end<b.end;     
     }
    return a.start<b.start;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),cmp);//排序
         vector<Interval>ans;//返回的结果数组
         int i = 0,n = intervals.size();
         int l,r;
         while(i < n){
              l = intervals[i].start;//用来表示当前区间左端的指针
              r = intervals[i].end; //用来表示当前区间右端的指针
             while(i<n-1&&r>=intervals[i+1].start){//合并区间
                 i++;//指针后移
                 r=max(r,intervals[i].end);
             }
             //将当前合并完的区间进行插入
             ans.push_back({l,r});
             i++;//指针后移
         }
         return ans;
    }
};

时间复杂度:O(n) 利用双指针将所有区间遍历
空间复杂度:O(n) 需要额外开辟空间来返回结果
优缺点:时间复杂度相比较算法二低一点,但是写起来麻烦

全部评论
排序的复杂度是O(Nlog2^N),时间复杂度哪来的O(N)?
11 回复 分享
发布于 2022-05-01 11:15
确实,排序时间复杂度是O(N)就有些离谱
1 回复 分享
发布于 2022-08-27 14:44 北京
这第一个和第二个有啥区别。。。没看出来。 我觉得本质上是一个算法
点赞 回复 分享
发布于 2024-06-19 11:06 四川
我有个思路就是把前面的区间向后面合并,不能合并的直接添加,如果元数据是正序,时间复杂的可以达到on,如果逆序最坏on2
点赞 回复 分享
发布于 2024-04-08 11:02 河南
时间复杂度为什么确定O(N)?
点赞 回复 分享
发布于 2022-06-18 17:13

相关推荐

缓解焦虑的最好方法是回家。鼠鼠昨天上午考完了本科阶段的最后一场考试,大概率考得稀烂,但是没多想,考完立马收拾行李,坐上了提前约好的顺风车飞奔回家。虽然家和学校很近,只有一百多公里的路程,但距离上次回家也已经有三四个月了。每次想回家,期间总有考试、毕业设计、面试、实习等等各种各样的原因,没办法回去,待在学校和公司的每一天也都充斥着无形的压力和焦虑。现在终于完成了答辩,考完了试,公司那边也请了假,是时候回去一趟了。没有提前通知爸妈,想给他们一个惊喜。下午提前到了家,他俩还在上班,只好让外公外婆来给我开门。因为我的回家,晚上外婆在厨房格外忙碌,做了满满一大桌子菜,填饱了我天天吃外卖的肚子。晚上也没空...
梦想是成为七海千秋:取决于家庭吧?其实回家更焦虑了,每天起床父母都问实习找好了没简历投递了没今天有没有面试,但是又没有什么结果,玩两下手机父母就会说你看你啥也没找到为什么天天就知道刷手机,怎么不去学习…我现在就希望我能永远在外面实习,报喜不报忧,等拿到一个好offer再回家
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
评论
15
4
分享

创作者周榜

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