Python, beats 94%. Thoughts?


  • 0
    S
    def findRightInterval(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[int]
            """
            if len(intervals) == 0: return []
            
            highStart = -sys.maxint #Highest start point
            lowStart = sys.maxint #Lowest start point
            for i in intervals:
                highStart = max(i.start,highStart)
                lowStart = min(i.start,lowStart)
            
            m = highStart - lowStart + 1 
            l = [-1] * m 
            #Construct list where the value at each index is the 
            #start value of interval i.
            for i in range(len(intervals)):
                l[intervals[i].start - lowStart] = i
            res = []
            #Backfill gaps in our start index list 
            prev = l[-1]
            for i in range(len(l)-1,0,-1):
                if l[i] == -1:
                    l[i] = prev
                else:
                    prev = l[i]
            #If the interval ends outside range, return -1 
            #else return value from index list
            for i in intervals:
                res.append(-1 if i.end - lowStart >= m else l[i.end - lowStart])
            return res
    

    I think this will scale pretty poorly if the range (between highStart and lowStart) is too large. What do you think?


Log in to reply
 

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