首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-56-合并区间

leetcode-56-合并区间

作者头像
chenjx85
发布2018-08-30 17:22:45
5890
发布2018-08-30 17:22:45
举报

题目描述:

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

要完成的函数:

* Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {}

vector<Interval> merge(vector<Interval>& intervals) 

说明:

1、这道题给定一个vector,里面装着多个Interval,Interval是一个struct结构。

比如[[1,3],[2,6],[8,10],[15,18]],[1,3]这个就是一个Interval,有start和end。

现在要求合并区间,比如上面举的这个例子,可以合并成[[1,6],[8,10],[15,18]]。

最终也是包含Interval的vector这种形式。

2、这道题很明显,我们可以先按照Interval的start来升序排列,假设给定的vector是[[2,4],[1,3],[5,6],[5,8]],我们先排序成[[1,3],[2,4],[5,6],[5,8]]。

这样我们判断一下前一个[1,3]和后一个[2,4]可不可以合并,可以的话把合并的结果存在后一个里面,修改成[1,4]。

接着再判断后一个[1,4]和再后一个[5,6]可不可以合并,不可以的话就把后一个存储在要返回的vector中。

接着再比较再后一个[5,6]和再再后一个[5,8]可不可以合并,可以就把合并的结果存在后一个里面,修改成[5,8]。

最后我们再push_bck给定vector的最后一个Interval到要返回的vector中。

代码如下:

    static bool cmp(Interval &a,Interval &b)//这里要加static
    {
        return a.start<b.start;//按照start来比较,升序排列
    }
    vector<Interval> merge(vector<Interval>& intervals) 
    {
        if(intervals.size()==0)return intervals;//边界条件
        vector<Interval> res;//要返回的vector
        sort(intervals.begin(),intervals.end(),cmp);//按照start升序排列
        for(int i=1;i<intervals.size();i++)//从i=1开始
        {
            if(intervals[i].start>intervals[i-1].end)//如果start大于前一位的end
                res.push_back(intervals[i-1]);//那么直接push_back前一位
            else//如果要合并区间
            {
                intervals[i].start=intervals[i-1].start;//修改当前interval的start
                intervals[i].end=max(intervals[i-1].end,intervals[i].end);//修改当前interval的end
            }
        }
        res.push_back(intervals.back());//最后记得要push_back最后一个
        return res;
    }

上述代码中,cmp函数前面要加static,定义为静态函数,不然会报错:invalid use of non-static member function 'bool Solution::cmp(Interval&, Interval&)'。

我也不懂为什么要加static的定义,对于这一块不是很熟悉……

另外,在cmp函数中,如果return a.start<=b.start,也就是把小于号换成小于等于号,同样报错,有一个测试样例跑不过,我也不知道为什么会跑不过。

照理来说都是一样的……如果有同学知道,烦请不吝赐教。

上述代码实测12ms,beats 96.53% of cpp submissions。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-08-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档