# Time-optimal python solution

• Although the asymptotic runtime will always be O(n) because we are inserting and deleting elements from an array, it is possible to do everything else in O(log n) time.

First, we write two helper functions to identify all intervals that are strictly left and strictly right of `newInterval`. (By strictly we mean completely nonoverlapping; not even sharing endpoints.) This can be done via binary search:

``````class Solution(object):

def last_left_interval(self, intervals, new_interval):
assert len(intervals) > 0
low = -1
high = len(intervals)
while high - low > 1:
mid = (low + high) // 2
if intervals[mid].end < new_interval.start:
low = mid
else:
high = mid
return low

def first_right_interval(self, intervals, new_interval):
assert len(intervals) > 0
low = -1
high = len(intervals)
while high - low > 1:
mid = (low + high) // 2
if intervals[mid].start > new_interval.end:
high = mid
else:
low = mid
return high
``````

These methods return the highest index of an interval left to `newInterval` that doesn't overlap it, and the lowest index of an interval right of `newInterval` that doesn't overlap it.

Now, we know that `newInterval` overlaps only those intervals between those two indices. All those intermediate intervals and `newInterval` will be merged into one interval. It's easy to find the new start and end bounds of this interval by checking the first and last intermediate intervals.

``````def insert(self, intervals, newInterval):
if len(intervals) == 0:
intervals.append(newInterval)
return intervals

# First, we must find all intervals strictly outside <newInterval>.
# <left> is the INDEX of the last interval to the left
# <right> is the INDEX of the first interval to the right
left = self.last_left_interval(intervals, newInterval)
right = self.first_right_interval(intervals, newInterval)
print('last_left: ' + str(left))
print('first_right: ' + str(right))

if right - left <= 1:
# No intervals overlap <newInterval>.
return intervals[:left+1] + [newInterval] + intervals[right:]

# <newInterval> overlaps with all intervals indexed between <left>
# and <right>. Therefore, all such intervals and newInterval will be
# replaced with a single interval.
new_left = min(newInterval.start, intervals[left + 1].start)
new_right = max(newInterval.end, intervals[right - 1].end)
return intervals[:left+1] + [Interval(new_left, new_right)] + intervals[right:]
``````

My time for this is 72 ms (87.41%).

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