难度: Hard
原题连接
内容描述
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].
思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******
因为原intervals是有序且non-overlapping的，所以打算直接用56题的代码AC，beats 73.53%
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
if not intervals or len(intervals) == 0:
return [newInterval]
res = []
for interval in sorted(intervals+[newInterval], key = lambda x: (x.start, x.end)):
if res and res[-1].end >= interval.start:
res[-1].end = max(res[-1].end, interval.end)
else:
res.append(interval)
return res思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
考虑到之前的题目条件中的intervals本身就是有序这个特征，觉得排序没有必要，只要先插入，再看看是否需要merge即可
这样时间复杂度减到了O(N), beats 97.49%
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
if not intervals or len(intervals) == 0:
return [newInterval]
idx = -1
for i in range(len(intervals)):
if intervals[i].start > newInterval.start:
idx = i
break
if idx != -1:
intervals.insert(i, newInterval)
else:
intervals.append(newInterval)
res = []
for interval in intervals:
if res and res[-1].end >= interval.start:
res[-1].end = max(res[-1].end, interval.end)
else:
res.append(interval)
return res思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******
寒神的二分法, beats 97.49%
from bisect import bisect_left, bisect
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
inter = [v for i in intervals for v in (i.start, i.end)]
start, end = newInterval.start, newInterval.end
i, j = bisect_left(inter, start), bisect(inter, end)
if i & 1:
i -= 1
start = inter[i]
if j & 1:
end = inter[j]
j += 1
inter[i:j] = [start, end]
return [Interval(s, e) for s, e in zip(inter[::2], inter[1::2])]