题目

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

 

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

 

思路:

1. 模拟题

2. Insert Interval 是 Merge Interval 的扩展, 将 newInterval 插入到 Intervals 即可转化成 Merge Interval

 

代码

bool sortInterval(const Interval &i1, const Interval &i2) {	return i1.start < i2.start;}class Solution {public:    vector
      
        merge(vector
       
         &intervals) {		vector
        
          newVec;		if(intervals.size() <= 0)			return newVec;				sort(intervals.begin(), intervals.end(), sortInterval);		for(int i = 0; i < intervals.size(); i ++) {			Interval nextInt = intervals[i];			if(i == intervals.size()-1) {				newVec.push_back(nextInt);				break;			}			Interval tmp = intervals[i+1];			while(tmp.start <= nextInt.end) {				nextInt.end = max(tmp.end, nextInt.end);				i++;				if(i+1