436.-find-right-intervalsolution.md

436. Find Right IntervalSolution

{% tabs %} {% tab title="Python" %}

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
    
        ## 本能做法，排序加二分
        ## 看来还不错，其他答案是红黑树， 大悟
        if len(intervals) <= 1: return [-1]
        sort = sorted(intervals,key = lambda x : x[0])
        ans = []
        dit = collections.defaultdict(int)
        for i,interval in enumerate(intervals):
            dit[tuple(interval)] = i
        print(sort)
        for i,(l, r) in enumerate(intervals):
            idx = self.binary(sort, r)
            ans.append(dit[tuple(sort[idx])] if idx != -1 else -1)
            
            
        return ans
    
    
    def binary(self, nums,target):
        l = 0
        r = len(nums)
        while l < r:
            mid = (l + r ) //2
            if nums[mid][0] >= target:
                r = mid
            else:
                l = mid + 1

        return -1 if l == len(nums) else l

{% endtab %} {% endtabs %}