Python solution with binary search, 112ms


  • 0
    C

    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

  • 0
    B

    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


Log in to reply
 

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