57. Insert Interval

Problem statement:

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 One:

Find the position for start and end position according to the value, obviously, this is a very complexity solution, we have to consider many situations, but we do not use extra spaces.

 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         bool b_start = false;
14         bool b_end = false;
15         
16         vector<vector<int>::size_type> merge_interval_idx;
17         Interval merge_interval;
18         
19         for(vector<int>::size_type ix = 0; ix < intervals.size(); ix++){
20             // find where is the position of start
21             if(!b_start){
22                 if(newInterval.start < intervals[ix].start){
23                     if(newInterval.end < intervals[ix].start){
24                         b_start = true;
25                         b_end = true;
26                         intervals.insert(intervals.begin() + ix, newInterval);
27                         return intervals;
28                     } else {
29                         // newInterval.end >= intervals[ix].start
30                         merge_interval.start = newInterval.start;
31                         newInterval.end = intervals[ix].end > newInterval.end ? intervals[ix].end : newInterval.end;
32                         b_start = true;
33                         merge_interval_idx.push_back(ix);
34                     }
35                 } else {
36                     // newInterval.start >= intervals[ix].start
37                     if(newInterval.start > intervals[ix].end){
38                         continue;
39                     } else {
40                         // find the position of start
41                         merge_interval.start = intervals[ix].start;
42                         newInterval.end = intervals[ix].end > newInterval.end ? intervals[ix].end : newInterval.end;
43                         merge_interval_idx.push_back(ix);
44                         b_start = true;
45                     }
46                 }
47             } else if(!b_end){
48                 // find where is the position of end
49                 if(newInterval.end >= intervals[ix].start){
50                     if(newInterval.end <= intervals[ix].end){
51                         merge_interval.end = intervals[ix].end;
52                         merge_interval_idx.push_back(ix);
53                         b_end = true;
54                     } else{
55                         // newInterval.end > intervals[ix].end
56                         merge_interval_idx.push_back(ix);
57                         continue;
58                     }
59                 } else {
60                     // newInterval.end < intervals[ix].start
61                     merge_interval.end = newInterval.end;
62                     b_end = true; 
63                     break;
64                 }
65             }
66         }
67         
68         // both start and end have not find their position
69         // push them back to the end of intervals
70         if(!b_start && !b_end){
71             intervals.push_back(newInterval);
72             return intervals;
73         }
74         
75         // start has found, however end has not found
76         // normally this situation happens: newInterval.end is greater than the end of last element
77         if(b_start && !b_end){
78            merge_interval.end = newInterval.end; 
79         }
80         
81         // delete already merged intervals
82         if(!merge_interval_idx.empty()){
83             cout<<"The merge interval is: "<<merge_interval_idx[0]<<endl;
84             intervals[merge_interval_idx[0]].start = merge_interval.start;
85             intervals[merge_interval_idx[0]].end = merge_interval.end;
86             
87             for(vector<int>::size_type ix = 1; ix < merge_interval_idx.size(); ix++){
88                 merge_interval_idx[ix] -= ix - 1;
89                 cout<<"The interval index is: "<<merge_interval_idx[ix]<<endl;
90             }
91         
92             for(vector<int>::size_type ix = 1; ix < merge_interval_idx.size(); ix++){
93                 intervals.erase(intervals.begin() + merge_interval_idx[ix]);
94             }    
95         }
96         return intervals;
97     }
98 };

Solution two:

This solution is very simple and easy to understand, the detailed analysis is shown in the following figure, the drawback of this solution is the space complexity is O(n).

we loop to enumerate all intervals in given array, each time, there are three situations for interval[ix] and newIntervals,

in case 1:

insert New into merged_list, and update newInterval to be current, and continue to put left intervals into merged_list

in case 2:

we should update the start and end position of newInterval with interval[ix], start = min(newInterval.start, interval[ix].start), end = max(newInterval.end, interval[ix].end);
continue to next element in intervals
push newInterval into the back of merged_list after the loop

In case 3:

insert the interval[ix] into merged_list and continue;

 1 class Solution {
 2 public:
 3     vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
 4         vector<Interval> merged_interval;
 5         for(vector<Interval>::size_type ix = 0; ix < intervals.size(); ix++){
 6             if(newInterval.end < intervals[ix].start){
 7                 merged_interval.push_back(newInterval);
 8                 newInterval = intervals[ix];
 9             } else if(newInterval.start > intervals[ix].end){
10                 merged_interval.push_back(intervals[ix]);
11             } else if(newInterval.end >= intervals[ix].start || newInterval.start <= intervals[ix].end){
12                 newInterval.start = min(intervals[ix].start, newInterval.start);
13                 newInterval.end = max(intervals[ix].end, newInterval.end);
14             }
15         }
16         
17         merged_interval.push_back(newInterval);
18         return merged_interval;
19     }
20 };