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

思路：

是的一个延伸问题，先看看怎么Merge

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 vector
     
       merge(vector
      
        &intervals) { 2     if(intervals.size() <= 1) 3         return intervals; 4          5     vector
       
         vres; 6     sort(intervals.begin(), intervals.end(), intvalcomp);//先对interval排序 7     Interval tmp(intervals[0]); 8     for(Interval it:intervals){ 9         if(tmp.start == it.start){10             tmp.end = it.end;11         }else if(tmp.end >= it.start){
   //intervals有序，必然有tmp.start < it->start12             if(tmp.end < it.end)//直接无视后者{[1,4],[2,3]}13                 tmp.end = it.end;//直接吞并后者{[1,3],[2,4]}14         }else{15             vres.push_back(tmp);//不相交16             tmp = it;17         }18     }19     vres.push_back(tmp);//漏掉这句会fail{[1,4],[1,4]}20     return vres;21 }22 23 bool intvalcomp(Interval a, Interval b){24     if(a.start == b.start)25         return a.end < b.end;26     else27         return a.start < b.start;28 }
       
      
     

现在有了这个Merge好了的不相交区间序列，怎么进行插入呢？Insert Interval条件太多，每一个大小等号比较，每一个小下标就能让人栽跟斗，因此它也是我目前最讨厌的题目，没有之一。

一开始尝试这种思路：

“新序列按照start排好序（start肯定是各不相同的），第一步我们先用二分找出有交集的序列片段的开始，这一点很像，然后再往后处理。”

脑子不清楚憋了一下午，恶心的我两天不能刷Leetcode，如果真要写出来的话，就老老实实下面这样，效率不一定差，因为看题目反正是不想要你改变输入参数，横竖都得遍历一遍来拷贝。挺有意思的是，晚上我看到了Google Campus的youku视频，讲述的就是一个倒霉孩子花了30min写二分Insert Interval的反例。。。

1 vector
     
       insert(vector
      
        &intervals, Interval newInterval) { 2     vector
       
         rs; 3     int i = 0; 4     while(i < intervals.size() && intervals[i].end < newInterval.start){
   //找到第一个起点 5         rs.push_back(intervals[i++]); 6     } 7     if(i == intervals.size()){
   //为空或过了结尾点   8         rs.push_back(newInterval); 9         return rs;10     }11     12     newInterval.start = min(newInterval.start, intervals[i].start);13     while(i < intervals.size() && intervals[i].start <= newInterval.end){
   //找到结束点 14         newInterval.end = max(newInterval.end, intervals[i++].end);15     }16     rs.push_back(newInterval);17 18     while(i < intervals.size()){19         rs.push_back(intervals[i++]);20     }21     return rs;22 }