Problem: 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: Insert Interval, Python:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-01-27 23:13:47
# @Author : NSSimacer
# @Version : 1.0
class Interval:
# Definition for an interval.
def __init__(self, s=0, e=0):
self.start = s
self.end = e
class Solution:
# @param intervals, a list of Intervals
# @param newInterval, a Interval
# @return a list of Interval
def insert(self, intervals, newInterval):
start = newInterval.start
end = newInterval.end
result = []
i = 0
while i < len(intervals):
if start <= intervals[i].end:
if end < intervals[i].start:
break
start = min(intervals[i].start, start)
end = max(intervals[i].end, end)
else:
result.append(intervals[i])
i += 1
result.append(Interval(start, end))
result += intervals[i:]
return result

时间复杂度O(N),空间复杂度O(N)。