57. Insert Interval

Originally, I was thinking of applying binary search to find the insertion point and then insert the new interval and update the new interval by merging following intervals and delete the merged intervals. However, this solution has many corner cases that I need to address for the insertion position. Additionally, the removing operation still has O(n) time. Therefore, I don’t think binary search is necessary in this case and we can deal with it from the beginning to end.

First of all, we scan the array from left to right and keep pushing intervals into result as long as intervals[i].end is less than newInterval.start, i.e. no overlap. Once an overlap is found, i.e. intervals[i].end >= newInterval.start, we keep updating the newInterval’s start and end pointing until intervals[i].start > newIntervals.end.

And in the end, we copy the rest intervals to the result.

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:      int i = 0;  
15:      while(i < intervals.size() && intervals[i].end < newInterval.start){  
16:        res.push_back(intervals[i++]);  
17:      }  
18:      while(i < intervals.size() && intervals[i].start <= newInterval.end){  
19:        newInterval.start = min(intervals[i].start, newInterval.start);  
20:        newInterval.end = max(intervals[i].end, newInterval.end);  
21:        i++;  
22:      }  
23:      res.push_back(newInterval);  
24:      while (i < intervals.size()) {  
25:        res.push_back(intervals[i++]);  
26:      }  
27:      return res;  
28:    }  
29:  };  

When I revisited the problem, I came up the solution with the same idea. But I made mistakes in
line 21: where I missed case that the newInterval could be inserted before the current interval in the list.

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:      int i = 0;  
15:      for (; i < intervals.size(); i++) {  
16:        if (intervals[i].end < newInterval.start) res.push_back(intervals[i]);  
17:        else break;  
18:      }  
19:      if (i == intervals.size()) { res.push_back(newInterval); return res; }  
20:      for (; i < intervals.size(); i++) {  
21:        if (newInterval.start > intervals[i].end || newInterval.end < intervals[i].start) break;  
22:        newInterval.start = min(newInterval.start, intervals[i].start);  
23:        newInterval.end = max(newInterval.end, intervals[i].end);  
24:      }  
25:      res.push_back(newInterval);  
26:      for (; i < intervals.size(); i++) {  
27:        res.push_back(intervals[i]);  
28:      }  
29:      return res;  
30:    }  
31:  };