首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >​关关的刷题日记99 – Leetcode 56. Merge Intervals

​关关的刷题日记99 – Leetcode 56. Merge Intervals

作者头像
WZEARW
发布2018-04-13 15:42:46
5430
发布2018-04-13 15:42:46
举报
文章被收录于专栏:专知专知

关关的刷题日记99 – Leetcode 56. Merge Intervals

题目

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

题目的意思是给出一个区间集合,让我们合并所有重叠区间。

思路

首先我们要对集合进行从小到大排序,因为区间是自己定义的数据结构,所以我们要自己定义排序函数。需要注意的是自定义排序时,sort中的比较函数compare要声明为静态成员函数或全局函数,不能作为普通成员函数,否则会报错:invalid use of non-static member function。 排好序之后遍历集合的每一个区间,如果后面的区间的左端点小于等于左边的区间的右端点,那么这两个区间就可以合并。

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

    class Solution {
    public:
        static


    bool
    cmp(Interval
    a, Interval
    b)
    {
    if (a.start != b.start)
    return a.start < b.start;
    else
    return a.end < b.end;
    }

    vector < Interval > merge(vector < Interval > & intervals) {
    vector < Interval > output;
    if (intervals.empty())
        return intervals;
    sort(intervals.begin(), intervals.end(), cmp);
    output.push_back(intervals[0]);
    for (int i=1; i < intervals.size();++i)
    {
    if (intervals[i].start <= output.back().end)
    output.back().end = max(intervals[i].end, output.back().end);
    else
    output.push_back(intervals[i]);
    }
    return output;
    }
    };

人生易老,唯有陪伴最长情,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-01-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 专知 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 思路
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档