1.题目基本信息

1.1.题目描述

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

区间 i 的 右侧区间 可以记作区间 j ，并满足 start_j >= end_i ，且 start_j 最小化 。注意 i 可能等于 j 。

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

1.2.题目地址

https://leetcode.cn/problems/find-right-interval/description

2.解题方法

2.1.解题思路

二分查找+排序

2.2.解题步骤

第一步,将原索引绑定到区间中,防止后面排序覆盖索引信息

第二步，将区间按起始值进行排序，并获取排序后的区间的第一个值的数组，这是用来后面的二分查找最近的右区间的

第三步，遍历。每次循环中，选出当前的区间curInterval，并根据当前区间的结尾值endVal+二分查找获取在排序区间中最近的右区间的索引，如果索引值大于等于length，那么说明没有哪一个区间的起始值大于endVal，则设置当前区间的-1，反之，设置为二分查找到的区间的原始索引值

3.解题代码

Python代码

import bisect

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        # 第一步,将原索引绑定到区间中,防止后面排序覆盖索引信息
        length=len(intervals)
        for i in range(length):
            intervals[i].append(i)
        # 第二步，将区间按起始值进行排序，并获取排序后的区间的第一个值的数组，这是用来后面的二分查找最近的右区间的
        intervals.sort()
        firstNums=[item[0] for item in intervals]
        # 第三步，遍历。每次循环中，选出当前的区间curInterval，并根据当前区间的结尾值endVal+二分查找获取在排序区间中最近的右区间的索引，如果索引值大于等于length，那么说明没有哪一个区间的起始值大于endVal，则设置当前区间的-1，反之，设置为二分查找到的区间的原始索引值
        result=[-1]*length
        for i in range(length):
            curInterval=intervals[i]
            endVal=curInterval[1]
            matchIndex=bisect.bisect_left(firstNums,endVal)
            if matchIndex<length:
                result[curInterval[2]]=intervals[matchIndex][2]
            else:
                result[curInterval[2]]=-1
        return result


        

4.执行结果