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

会员服务 ·

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

专知内容组（编）

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记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;
    }
    };