LeetCode Merge Intervals

タイトル
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] .
 
指定された区間をマージ
1、区間ヘッダの増分順に並べ替える;
2、最初から後ろへスキャン:仮区間を0番目の区間とする
2.1、後の区間の先頭が臨時区間の末尾より小さく、両者を合併する.
2.2、後の区間の先頭が臨時区間の末尾より大きく、臨時区間を出力結果に挿入し、後の区間を新しい臨時区間とする.
 
コード:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool cm(const Interval &i1,const Interval &i2);	//        

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
		vector<Interval> ans;
        sort(intervals.begin(),intervals.end(),cm);	//  
		int len=intervals.size();
		if(len==0)
			return ans;
		Interval itemp;	//    ，      
		itemp.start=intervals[0].start;
		itemp.end=intervals[0].end;
		for(int i=1;i<len;i++)	//  ，  
		{
			if(intervals[i].start<=itemp.end)	//          ，  
				itemp.end=max(intervals[i].end,itemp.end);
			else	//     ，  ，     
			{
				ans.push_back(itemp);
				itemp.start=intervals[i].start;
				itemp.end=intervals[i].end;
			}
		}
		ans.push_back(itemp);	//      
		return ans;
    }
};

bool cm(const Interval &i1,const Interval &i2)
{
	return i1.start<i2.start;
}