The idea is to figure out the insert position for both the start and end values of the new interval. Took me a lot of time to figure out all the cases, but the final solution is not hard to read.

```
def insert(self, intervals, newInterval):
new_start, new_end = newInterval.start, newInterval.end
intervals = [Sentinel(float('-inf'), float('-inf'))] + intervals + [Sentinel(float('inf'), 0)]
l = len(intervals)
start_position = self.search(intervals, 0, l, new_start)
end_position = self.search(intervals, start_position, l, new_end)
if new_start <= intervals[start_position - 1].end:
new_start = intervals[start_position - 1].start
start_position -= 1
new_end = max(new_end, intervals[end_position - 1].end)
if new_end == intervals[end_position].start:
new_end = intervals[end_position].end
end_position += 1
intervals[start_position: end_position] = [Interval(new_start, new_end)]
return intervals[1:-1]
def search(self, intervals, low, high, target):
while low <= high:
mid = low + (high - low) // 2
val = intervals[mid].start
if val == target:
return mid
elif val < target:
low = mid + 1
else:
high = mid - 1
return low
class Sentinel:
def __init__(self, x=0, y=0):
self.start = x
self.end = y
```