Insert interval
August 7, 2022
intervalsProblem URL: Insert interval
We will go through each interval, and compare the end of the new interval with the start of the current interval, if it doesn't collide, then just insert the new interval. Else, merge the interval with the new interval and append it to the result.
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [
min(newInterval[0], intervals[i][0]),
max(newInterval[1], intervals[i][1]),
]
res.append(newInterval)
return res
Time Complexity: O(n)
Space Complexity: O(1)