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.
Indeed. Good references here:
https://leetcode.com/problems/insert-interval/
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
The solution fails to take into account intervals is already sorted. therefore, sorting again is unnecessary. Better to use a linear or binary search to find the correct location of the new interval and merge if necessary, with overlapping intervals. That will give O(n) solution.