# Python solution with binary search, 112ms

• 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``````

• This does use the binary-search to have log(n) complexity there. But the slice set statement "intervals[start_position: end_position] = [Interval(new_start, new_end)]" takes O(n) time. In python, both list copy & slice setting have an O(n) complexity. I really doubt whether we can find a log(n) solution. Please refer to : https://wiki.python.org/moin/TimeComplexity

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.