Since the intervals are already sorted, we should take advantage of that and come up with a solution that runs in O(n) Instead of O(nlogn) (sorting). We can simply skip all the intervals that are before the new one, then merge all the intervals that overlap with the new one and then add the remaining intervals
I think the last solution fails on the test case:
intervals = [[1,2],[3,4],[6,7],[8,10],[12,16], [4.1, 5], [7.1, 7.5]]
new_interval = [4, 4.5]
the solution outputs [[1, 2], [3, 4.5], [6, 7], [8, 10], [12, 16], [4.1, 5], [7.1, 7.5]], but it’s still overlapping.
Test cases here don’t cover much. Absolutely have to test on https://leetcode.com/problems/insert-interval
O(log n) + two pointers solution:
def insert_interval(intervals: List[List[int]], new_interval: List[int]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
left_idxs = [x[0] for x in intervals]
idx = bisect_right(left_idxs, new_interval[0])
intervals.insert(idx, new_interval)
right = idx + 1
left = idx - 1
# merge to the right
while idx + 1 < len(intervals) and has_overlap(intervals[idx], intervals[idx + 1]):
__next = intervals.pop(idx + 1)
intervals[idx] = [
min(intervals[idx][0], __next[0]),
max(intervals[idx][1], __next[1]),
]
while idx - 1 >= 0 and has_overlap(intervals[idx - 1], intervals[idx]):
__previous = intervals.pop(idx - 1)
idx -= 1
intervals[idx] = [
min(intervals[idx][0], __previous[0]),
max(intervals[idx][1], __previous[1]),
]
return intervals
My solution in O(N). Simple loop through the intervals.
def insert_interval(intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
before = []
after = []
for interval in intervals:
if interval[1] < new_interval[0]:
before.append(interval)
elif interval[0] > new_interval[1]:
after.append(interval)
else:
new_interval[0] = min(new_interval[0], interval[0])
new_interval[1] = max(new_interval[1], interval[1])
res = before + [new_interval] + after
return res