1. 056

merge-intervals/

2. 算法O

• O(nm)

http://www.cnblogs.com/grandyang/p/4370601.html

3. 代码

/**

* 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:

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

        vector<Interval>  res;

        if(intervals.empty())  return res;

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

        res.push_back(intervals[0]);

        for(int i=1;i<intervals.size();++i){

            if(res.back().end>=intervals[i].start)

                res.back().end=max(res.back().end,intervals[i].end);

            else

                res.push_back(intervals[i]);

        }

        return res;

    }

private:

    static bool comp(const Interval& a,const Interval& b){

        return (a.start<b.start);

    }

};