Easy to understand Python Binary Search Solution


  • 0
    S

    Modified based on the neat O(n) solution of Stefan.

    # Definition for an interval.
    # class Interval(object):
    #     def __init__(self, s=0, e=0):
    #         self.start = s
    #         self.end = e
    
    class Solution(object):
        def insert(self, intervals, newInterval):
            # log(n)
            # find the largest index that interval i.end < s
            def binarySearch1(intervals, s, l, r):
                ret = -1
                while l<=r:
                    mid = l+r >>1
                    if intervals[mid].end < s:
                        ret = mid
                        l=mid+1
                    else:
                        r=mid-1
                return ret
            # smallest i such that i.start > e
            def binarySearch2(intervals, e, l, r):
                ret = -1
                while l<=r:
                    mid = l+r >>1
                    if intervals[mid].start > e:
                        ret = mid
                        r=mid-1
                    else:
                        l=mid+1
                return ret
            s = newInterval.start
            e = newInterval.end
            left = intervals[:binarySearch1(intervals, s, 0, len(intervals)-1)+1]
            index_right = binarySearch2(intervals, e, 0, len(intervals)-1)
            right = intervals[index_right:] if index_right != -1 else []
            if len(left) + len(right) != len(intervals):
                # megre
                s = min(intervals[len(left)].start, s)
                e = max(intervals[~len(right)].end, e)
            return left + [Interval(s,e)] + right
            
    

Log in to reply
 

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