原题网址：

描述

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

您在真实的面试中是否遇到过这个题？  是

样例

Given intervals => merged intervals:

[                     [  (1, 3),               (1, 6),  (2, 6),      =>       (8, 10),  (8, 10),              (15, 18)  (15, 18)            ]]

挑战

O(n log n) 的时间和 O(1) 的额外空间。

 

思路：

时间复杂度O(n log n) 应该是快排序了，可使用自带的sort函数，排序的是区间的start参数，按照从小到大的顺序。

参考：

排序后是合并，将intervals的第一个区间（start最小区间）压入result中。然后是下标从1开始遍历intervals，如果当前区间的start小于等于结果中最后一个区间的end，两个区间有重叠，结果中区间的end取二者中较大值，否则，将当前区间压入结果数组中。

AC代码：

/** * Definition of Interval: * classs Interval { *     int start, end; *     Interval(int start, int end) { *         this->start = start; *         this->end = end; *     } * } */class Solution {public:    /**     * @param intervals: interval list.     * @return: A new interval list.     */    vector
        
          merge(vector
         
           &intervals) {        // write your code here    vector
          
            result;    int n=intervals.size();    if (n==0)    {        return result;    }    sort(intervals.begin(),intervals.end(),cmp);    result.push_back(intervals[0]);    for (int i=1;i
           
            =intervals[i].start)        {            result.back().end=(result.back().end>intervals[i].end)?result.back().end:intervals[i].end;        }        else        {            result.push_back(intervals[i]);        }    }    return result;    }       static bool cmp(Interval a,Interval b){    return a.start
           
          
         
        

关于sort自定义比较函数，可参考：

本题中定义的CMP函数需要加 static ，至于为什么我也很费解。我只知道加了static后cpm函数没有this指针……

可参考：

    写在类内时，要加上static，lexicographical_compare 最后要求的是一个普通函数指针，而不是成员函数指针，所以要加static。

另外，若将CMP函数放在solution类外定义成全局函数也可以编译通过，如