Problem description:

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Solution:

See it as another interval, add to the list, sort it then merge intervals

1
2
3
4
5
6
7
8
9
def insert1(self, intervals, newInterval):
    intervals.append(newInterval)
    res = []
    for i in sorted(intervals, key=lambda x:x.start):
        if res and res[-1].end >= i.start:
            res[-1].end = max(res[-1].end, i.end)
        else:
            res.append(i)
    return res

$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        for index, i in enumerate(intervals):
            if i[1] < newInterval[0]:
                res.append(i)
            elif i[0] > newInterval[1]:
                res.append(newInterval)
                return res+intervals[index:]
            else:
                newInterval[0] = min(newInterval[0], i[0])
                newInterval[1] = max(newInterval[1], i[1])
        res.append(newInterval)
        return res

$O(n)$

This is a follow up for .

  1. Create a vector for storing result.
  2. If an end of an interval does not greater than newInterval’s start, then we know they are not intersecting. Since the input is sorted, we can put these into the result first.
  3. If an interval’s start is smaller than newInterval’s end, then they must intersect.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 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) {
        int index= 0;
        vector<Interval> res;
        while(index< intervals.size() && intervals[index].end < newInterval.start){
            res.push_back(intervals[index++]);
        }
        
        while(index< intervals.size() && newInterval.end>= intervals[index].start){
            newInterval.start= min(intervals[index].start, newInterval.start);
            newInterval.end= max(intervals[index].end, newInterval.end);
            index++;
        }
        res.push_back(newInterval);
        
        while(index< intervals.size())
            res.push_back(intervals[index++]);
        
        return res;
    }
};

time complexity: O(n)

Solution 2:

The idea is to use newInterval as a buffer, and update it when there’s an overlap.
When the newInterval.end < intervals[i].start, it means the upcoming intervals are greater, and no need to keep tracing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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;
        auto it= intervals.begin();
        for(; it!= intervals.end(); it++){
            if(newInterval.end < (*it).start)
                break;
            else if(newInterval.start > (*it).end)
                res.push_back(*it);
            else{ //overlapping, use newInterval as a buffer and update it
                newInterval.start= min(newInterval.start, (*it).start);
                newInterval.end= max(newInterval.end, (*it).end);
            }
        }
        
        res.push_back(newInterval);
        for(; it!= intervals.end(); it++){
            res.push_back(*it);
        }
        
        return res;
    }
};

reference:
https://goo.gl/5stsBW