LeetCode--Insert Interval

 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 };