题目

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].

分析

给定几个区间，要求合并重叠区间，返回结果；

AC代码

/**

 * Definition for an interval.

 * struct Interval {

 *     int start;

 *     int end;

 *     Interval() : start(0), end(0) {}

 *     Interval(int s, int e) : start(s), end(e) {}

 * };

 */

//自定义Interval类型元素的升序比较函数

bool cmp(Interval a, Interval b)

{

    return a.start < b.start;

}

class Solution {

public: 

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

        //如果输入参数为空，则返回空vector

        if (intervals.empty())

            return vector<Interval>();

        int len = intervals.size();

        //首先，按照每个Integerval的区间首值进行排序，自定义比较

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

        //声明结果

        vector<Interval> ret;

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

        //定义临时变量

        Interval temp = intervals[0];

        for (int i = 0; i < len; i++)

        {

            //换一种判断方法

            if (intervals[i].start > temp.end)

            {

                ret.push_back(temp);

                temp = intervals[i];

            }

            else{

                temp.end = temp.end > intervals[i].end ? temp.end : intervals[i].end;

            }//else

        }//for

        ret.push_back(temp);

        return ret;

    }

};

GitHub测试程序源码