Insert interval#
Practice Link#
LeetCode
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.
Examples#
1Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
2Output: [[1,5],[6,9]]
1Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
2Output: [[1,2],[3,10],[12,16]]
3Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Python Solution#
1class Solution(object):
2 def insert(self, intervals, newInterval):
3 """
4 :type intervals: List[List[int]]
5 :type newInterval: List[int]
6 :rtype: List[List[int]]
7 """
8 s, e = newInterval[0], newInterval[-1]
9 left, right = [], []
10 for i in intervals:
11 if i[-1] < s:
12 left += i,
13 elif i[0] > e:
14 right += i,
15 else:
16 s = min(s, i[0])
17 e = max(e, i[-1])
18 return left + [[s, e]] + right