Interval Insert

来源：Leetcode

原帖：http://oj.leetcode.com/problems/insert-interval/

题目：
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].
Solution: For example 2:
           1. compare [1,2] with [4,9], then insert [1,2];
           2. merge [3,5] with [4,9], get newInterval = [3,9];
           3. merge [6,7] with [3,9], get newInterval = [3,9];
           4. merge [8,10] with [3,9], get newInterval = [3,10];
           5. compare [12,16] with [3,10], insert newInterval [3,10], then all the remaining intervals...


代码：

 /**  
  * 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:  
   vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {  
     vector<Interval> res;  
     if (intervals.empty()) {  
       res.push_back(newInterval);  
       return res;  
     }  
     bool inserted = false;  
     for (int i = 0; i < intervals.size(); ++i) {  
       if (inserted || intervals[i].end < newInterval.start) { // non-overlaping  
         res.push_back(intervals[i]);  
       } else if (newInterval.end < intervals[i].start) {  
         res.push_back(newInterval);  
         res.push_back(intervals[i]);  
         inserted = true;  
       } else { // update new interval  
         newInterval.start = min(intervals[i].start, newInterval.start);  
         newInterval.end = max(intervals[i].end, newInterval.end);  
       }  
     }  
     if (!inserted) res.push_back(newInterval);        
     return res;  
   }  
 };