寻找右区间的思路探讨与源码
寻找右区间的题目如下图，该题属于数组类和搜索类型的题目，主要考察对于搜索方法的使用和数组结构的理解。本文的题目作者想到2种方法，分别是双指针方法和二分查找方法，其中双指针方法使用Java进行编写，而二分查找方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。
本人认为该题目可以使用双指针方法的思路进行解决，首先计算数组的长度，并初始化两个长度和数组等长的宽度为2的二维数组，然后开始遍历二维数组并进行赋值，把原始数组的第一列元素和下标赋值给第一个二维数组，把原始数组的第二列元素和下标赋值给第二个二维数组，再将两个二维数组进行排序。初始化一个1维数组，开始遍历循环并进行搜索，如果满足条件就把下标加1，如果下标小于数组长度，就把第一个数组的第二列值赋值给对应位置的1维数组，否则就赋值为-1，直到遍历结束并返回该数组。那么按照这个思路我们的Java代码如下：
#喷火龙与水箭龟
class Solution {public int[] findRightInterval(int[][] intervals) {int numLen = intervals.length;int[][] startIntervals = new int[numLen][2];int[][] endIntervals = new int[numLen][2];for (int ir = 0; ir < numLen; ir++) {startIntervals[ir][0] = intervals[ir][0];startIntervals[ir][1] = ir;endIntervals[ir][0] = intervals[ir][1];endIntervals[ir][1] = ir;}Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);Arrays.sort(endIntervals, (o1, o2) -> o1[0] - o2[0]);int[] res = new int[numLen];for (int ic = 0, jc = 0; ic < numLen; ic++) {while (jc < numLen && endIntervals[ic][0] > startIntervals[jc][0]) {jc = jc + 1;}if (jc < numLen) {res[endIntervals[ic][1]] = startIntervals[jc][1];} else {res[endIntervals[ic][1]] = -1;}}return res;}
}
显然，我们的双指针方法的效果一般，还可以用二分查找方法进行解决。首先遍历数组并把数组的下标加入到数组的末尾，将数组进行排序。计算数组的长度，初始化一个和数组长度一样的元素都是-1的数组，开始遍历循环，使用二分库查找函数找到下标，判断下标是否小于数组长度，如果是的话就把数组的元素赋值给一维数组的对应元素，按照这个思路直到遍历结束并返回结果。所以按照这个思路就可以解决，下面是Python代码：
#喷火龙与水箭龟
class Solution:def findRightInterval(self, intervals: List[List[int]]) -> List[int]:for ir, interval in enumerate(intervals):interval.append(ir)intervals.sort()numLen = len(intervals)res = [-1] * numLenfor _, end, id in intervals:ir = bisect_left(intervals, [end])if(ir < numLen):res[id] = intervals[ir][2]return res
从结果来说Java版本的双指针方法的效率一般，而Python版本的二分查找方法的速度比较不错，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。
