Insert Interval (C++ code)

LeetCode Insert Interval, Mar 27 '12
 难度4，出现频率5
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].
 思路： 我写的这个好复杂呀。。(后面有简单的)
* struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
       int from =0, to =0,i,left,right;

 if(intervals.empty() || newInterval.end < intervals[0].start){

      intervals.insert(intervals.begin(), newInterval);

      return intervals;

}

if(newInterval.start > intervals.back().end){

  intervals.push_back(newInterval);

  return intervals;

}

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

         if(newInterval.start < intervals[i].start){

             if(i > 0 && newInterval.start <= intervals[i-1].end) {

                from = i-1;

                left = intervals[i-1].start;

             }

             else{

               from = i;

               left = newInterval.start;

            }

             break;

        }
        from = i;
        left = intervals[i].start;

    }

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

         if(newInterval.end < intervals[i].end){

            if(i > 0 && newInterval.end < intervals[i].start) {

              to = i - 1;

              right =newInterval.end;

            }

          else{

             to = i;

             right = intervals[i].end;

          }
          break;

        }
        to = i;
        right = newInterval.end;

    }

Interval *toadd = new Interval(left,right);  

intervals.erase(intervals.begin() + from, intervals.begin() + to + 1);

intervals.insert(intervals.begin() + from, *toadd);

return intervals;
    }


简单版： 为毛别人能写的如此简单呢，学习~~下面这个是从luckynoob那里看来的（稍作修改）。

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 

   vector<Interval> res; 
   int i=0;
   int n = intervals.size(); 
 
   while(i < n && newInterval.start > intervals[i].end)
      res.push_back(intervals[i++]);
 
   if(i < n) newInterval.start = min(newInterval.start, intervals[i].start);
 
   while( i < n && newInterval.end >= intervals[i].start ) 
        i++;
 
   if(i > 0) newInterval.end =  max(newInterval.end, intervals[i-1].end);
 
   res.push_back(newInterval); 
 
   while(i < intervals.size())
 
      res.push_back(intervals[i++]);
 
 return res;
 
} 

然后我又写了个修改输入array不需要额外空间的： 

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {    
   int i=0, from, to;
   int n = intervals.size(); 
 
   while(i < n && newInterval.start > intervals[i].end)
      i++;
   from = i; 
   if(i < n) newInterval.start = min(newInterval.start, intervals[i].start);
 
   while( i < n && newInterval.end >= intervals[i].start ) 
        i++;
   to = i - 1;
   if(i > 0) newInterval.end =  max(newInterval.end, intervals[i-1].end); 
 
   if(from <= to) intervals.erase(intervals.begin()+ from, intervals.begin()+ to + 1);

   intervals.insert(intervals.begin()+from, newInterval); 

  
 return intervals;
 
}