LC 0436 [M] Find Right Interval - ALawliet/algorithms GitHub Wiki

two heaps

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        maxStartHeap = []
        maxEndHeap = []
        
        result = [0 for x in range(n)]
        
        for endIndex in range(n):
            heappush(maxStartHeap, (-intervals[endIndex][0], endIndex))
            heappush(maxEndHeap, (-intervals[endIndex][1], endIndex))
            
        for _ in range(n):
            topEnd, endIndex = heappop(maxEndHeap)
            result[endIndex] = -1
            if -maxStartHeap[0][0] >= -topEnd:
                topStart, startIndex = heappop(maxStartHeap)
                while maxStartHeap and -maxStartHeap[0][0] >= -topEnd:
                    topStart, startIndex = heappop(maxStartHeap)
                result[endIndex] = startIndex
                heappush(maxStartHeap, (topStart, startIndex))
                
        return result

binary search

def findRightInterval(self, intervals):
    l = sorted((e.start, i) for i, e in enumerate(intervals))
    res = []
    for e in intervals:
        r = bisect.bisect_left(l, (e.end,))
        res.append(l[r][1] if r < len(l) else -1)
    return res