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%).