Python with binary search


  • 0
    B
    # Definition for an interval.
    # class Interval(object):
    #     def __init__(self, s=0, e=0):
    #         self.start = s
    #         self.end = e
    from bisect import bisect
    class Solution(object):
        def findRightInterval(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[int]
            """
            retVal = []
            if len(intervals) < 2:
                    return [-1]
            tmp = []
            for idx, val in enumerate(intervals):
                    tmp.append((val.start, idx))
            tmp = tmp+[(float('Inf'), -1)]
            tmp.sort(key=lambda x: x[0])
            retVal = [tmp[self.binarysearch(tmp, I.end)][1] for I in intervals] 
            return retVal
            
        def binarysearch(self, l, x):
            left = 0
            right = len(l)-1
            while True:
                if left > right:
                    return left
                mid = (right+left)/2
                if l[mid][0] < x:
                    left = mid+1
                elif l[mid][0] > x:
                    right = mid-1
                else:
                    return mid if mid <= len(l)-1 else len(l)-1
    

Log in to reply
 

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