LC57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

    def insert(self, intervals: 'List[Interval]', newInterval: 'Interval') -> 'List[Interval]':
        res = []
        #if we haven't got to newInterval, add the intervals 
        i = 0
        while i < len(intervals) and intervals[i].end < newInterval.start:
            res.append(intervals[i])
            i += 1

        #now interval[i] intersect newInterval
        left = newInterval.start
        right = newInterval.end
        while i < len(intervals) and intervals[i].start <= newInterval.end:
            left = min(left, intervals[i].start)
            right = max(right, intervals[i].end)
            #print('left is ', left)
            i += 1

        res.append(Interval(left, right))

        while i < len(intervals):
            res.append(intervals[i])
            i += 1

        return res

We first traverse the intervals till when we either finish iterating or when interval[i] intersect with the newInterval.

We then keep iterating through the intervals. For each intervals, if it intersects with newInterval, we update the left and right of the merged interval.

WHy we keep left’s update inside the while loop.

It will simplify the code:
Imagine insert [1,2] into A = []. Then any i would be undefined for A. Updating left outside would means we need an extra if condition.
Like

        if i < len(intervals):
            left = min(newInterval.start, intervals[i].start)
        else:
            left = newInterval.start

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax