Time-optimal python solution


  • 0
    M

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


Log in to reply
 

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