LintCode 156: Merge Interval

题目描述

给出若干闭合区间，合并所有重叠的部分。

样例

给出的区间列表 => 合并后的区间列表：

[                     [

  [1, 3],               [1, 6],

  [2, 6],      =>       [8, 10],

  [8, 10],              [15, 18]

  [15, 18]            ]

]

Fri Feb 24 2017

思路

首先将区间们按照开始元素的大小排序，然后从头到尾遍历一遍，若遇到该区间的开始元素小于前一个区间的结束元素时，将两个区间合并。

区间合并可以直接修改前一个区间的结束元素的值，然后将该区间删除，达到\(O(1)\)的空间复杂度。

时间复杂度是\(O(nlogn)\)，偷懒没有写排序算法，直接调用库函数实现的。

代码

// 合并区间

// 用于排序开始时间的比较函数

static bool cmp(const Interval& x, const Interval& y)

{

    return x.start < y.start;

}

// 主执行函数

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

{

    if (intervals.size() <= 1) return intervals;

    sort(intervals.begin(), intervals.end(), cmp);

    for (vector<Interval>::iterator iter = intervals.begin() + 1;

        iter != intervals.end(); ++iter)

    {

        if (iter->start <= (iter - 1)->end)

        {

            if ((iter - 1)->end < iter->end)

                (iter - 1)->end = iter->end;

            intervals.erase(iter);

            --iter;

        }

    }

    return intervals;

}