20220609 leetcode 436 寻找最右区间

中等难度

问题

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。

区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。

返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

示例 1：

输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-right-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1- 通过-分值较低

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        ans = [-1]*len(intervals)
        tp = []
        left = []
        index = {}
        for i,[l,r] in enumerate(intervals):
            left.append(l)
            index[l] = i
        left.sort()
        for i,[l,r] in enumerate(intervals):
            for ll in left:
                if ll>=r:
                    ans[i] = index[ll]
                    break
        return ans

解法2- 超时

from typing import List
class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        left = []
        ans = []
        for i,[l,r] in enumerate(intervals):
            heapq.heappush(left,(l,r,i))
        for i,[l,r] in enumerate(intervals):
            aa = -1
            tmp = deepcopy(left)
            while tmp:
                ll = heapq.heappop(tmp)
                if ll[0] >= r:
                    aa = ll[2]
                    break
            ans.append(aa)
        return ans

原因是：在给ans赋值的时候，解法1只需要排序一次，解法2要排序n次

优化- todo

二分查找

双指针