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].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
题目大意：
给出一个二元组构成的区间数组, 在其中插入一个新的区间, 使得新的区间插入后, 数组也应当满足严格升序并且区间之间没有重叠.
解题思路：
若将新区间直接插入到区间数组中就是第56题的合并区间的题目，解题思路如下：https://www.jianshu.com/p/67935d04b104
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.append(newInterval)
intervals.sort()
if len(intervals) == 1:
return intervals
res = []
for i in range(len(intervals)):
if res == []:
res.append(intervals[i])
else:
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(intervals[i][1], res[-1][1])
else:
res.append(intervals[i])
return res
其他思路分区间讨论
- 不重叠部分
- intervals[i]右边小于newInterval左边，将intervals[i]置左
- newInterval右边小于intervals[i]左边，将intervals[i]置右
- 重叠部分
- 将中间重叠区间合并
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if len(intervals) == 0:
return [newInterval]
left = []
right = []
l = newInterval[0]
r = newInterval[1]
for i in range(len(intervals)):
if intervals[i][1] < newInterval[0]:
left.append(intervals[i])
elif newInterval[1] < intervals[i][0]:
right.append(intervals[i])
else:
l = min(intervals[i][0], newInterval[0], l)
r = max(intervals[i][1], newInterval[1], r)
return left + [[l, r]] + right
参考：https://blog.csdn.net/Wayne_Mai/article/details/80289874
解该题过程中遇到的问题及python误区：https://www.jianshu.com/p/eee82a92fe43
