Description
Insert a closed interval into sorted, disjoint closed intervals, merging any overlaps.
Solution
def insert(intervals, newInterval):
result = []
start,end = newInterval
i = 0
while i < len(intervals) and intervals[i][1] < start:
result.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][0] <= end:
start,end = min(start,intervals[i][0]),max(end,intervals[i][1])
i += 1
result.append([start,end])
result.extend(intervals[i:])
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1,2],[5,7]],[2,6]]- Output
[[1,7]]
The new interval bridges both existing intervals.
Example 2
- Input
[[],[3,4]]- Output
[[3,4]]
There are no existing intervals to merge.
Example 3
- Input
[[[1,2]],[4,5]]- Output
[[1,2],[4,5]]
A gap separates the two intervals.
Approach
Copy intervals before the new one, absorb touching intervals, then append the untouched suffix.
Time & space
O(n) time; O(n) output space, O(1) auxiliary space in Java and O(n) slicing overhead in Python. Here n is the input length.