本文共 2022 字，大约阅读时间需要 6 分钟。

struct Interval {	int start;	int end;	Interval() : start(0), end(0) {}	Interval(int s, int e) : start(s), end(e) {}};class Solution {//first sort and then merge, O(nlogn)public:	struct comp	{		bool operator()(const Interval& lhs, const Interval& rhs) const		{			if(lhs.start != rhs.start) return lhs.start < rhs.start;			else return lhs.end < rhs.end;		}	};	vector
   
     merge(vector
    
      &intervals) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		if(intervals.size() == 0) return vector
     
      ();		sort(intervals.begin(), intervals.end(), comp());		vector
      
        ans;		Interval tmp = intervals[0];		for (int i = 1; i < intervals.size(); ++i)		{			if(intervals[i].start <= tmp.end)				tmp.end = max(tmp.end, intervals[i].end);			else 			{				ans.push_back(tmp);				tmp = intervals[i];			}		}		ans.push_back(tmp);		return ans;	}};
      
     
    
   

second time

/** * 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:    struct cmp    {        bool operator()(const Interval& a, const Interval& b)const        {            if(a.start == b.start) return a.end < b.end;            else return a.start < b.start;        }    };        vector
   
     merge(vector
    
      &intervals) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        sort(intervals.begin(), intervals.end(), cmp());        vector
     
       newIntervals;        for(int i = 0; i < intervals.size();)        {            int newEnd = intervals[i].end;            int j;            for(j = i; j < intervals.size(); ++j)            {                if(intervals[j].start <= newEnd) newEnd = max(newEnd, intervals[j].end);                else break;            }            newIntervals.push_back(Interval(intervals[i].start, newEnd));            i = j;        }                return newIntervals;    }};
     
    
   

转载地址：http://mlxti.baihongyu.com/