Python solution with binary search, 112ms

  • 0

    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 =, 0, l, new_start)
        end_position =, 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
                high = mid - 1
        return low    
    class Sentinel:
        def __init__(self, x=0, y=0):
            self.start = x
            self.end = y

  • 0

    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 :

Log in to reply

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