1 class Solution { 2 public: 3     vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6     //Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. 7         //check input; 8         int sz = intervals.size(); 9         vector<Interval> res;10         11         for(int i=0; i<sz; i++) {12             if(intervals[i].end < newInterval.start) {13                 res.push_back( intervals[i]);14             } else if( intervals[i].start > newInterval.end) {15                 res.push_back( newInterval);16                 res.insert(res.end(), intervals.begin()+i, intervals.end() );17                 return res;18             } else {19                 newInterval.start = min(newInterval.start, intervals[i].start);20                 newInterval.end = max(newInterval.end, intervals[i].end);21             }22         }23         res.push_back(newInterval); 24         return res;25     }

 1 /** 2  * Definition for an interval. 3  * struct Interval { 4  *     int start; 5  *     int end; 6  *     Interval() : start(0), end(0) {} 7  *     Interval(int s, int e) : start(s), end(e) {} 8  * }; 9  */10 class Solution {11 public:12     vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {13         vector<Interval> res;14         if(intervals.size() == 0){15             res.push_back(newInterval);16             return res;17         }18         19         int newS = newInterval.start;20         int newE = newInterval.end;21         22         int indS = findIndex(newS,intervals);23         int indE = findIndex(newE,intervals);24         if(indS == -1 && indE != -1){25             Interval tmp(newS,intervals[indE].end);26             res.push_back(tmp);27             for(int i = indE+1 ; i < intervals.size() ; ++i){28                 res.push_back(intervals[i]);29             }30         }31         else if(indS != -1 && indE == -1){32             for(int i = 0 ; i < indS ; ++i){33                 res.push_back(intervals[i]);34             }35             Interval tmp(intervals[indS].start,newE);36             res.push_back(tmp);37         }38         else if(indS != -1 && indE != -1){39             int i;40             for(i = 0 ; i < indS ; ++i){41                 re.push_back(intervals[i]);42             }43             Interval tmp(intervals[indS].start,intervals[indE].end);44             res.push_back(tmp);45             for(i = indE+1 ; i < intervals.size() ; ++i){46                 res.push_back(intervals[i]);47             }48         }49         else{50             if(newS > intervals[intervals.size()-1].end){51                 52             }53         }54         return res;55     }56     int findIndex(int val,vector<Interval> &intervals){57         int left = 0;58         int right = intervals.size()-1;59         while(left <= right){60             int mid = left + (right - left)>>1;61             if(intervals[mid].start <= val && intervals[mid].end >= val){62                 return mid;63             }64             else if(val > intervals[mid].end){65                 left = mid+1;66             }67             else{68                 right = mid-1;69             }70         }71         return -1;72     }73 };