题目

https://leetcode.com/problems/find-right-interval/

题解

这题考察点不难，就是个普通的二分查找。详细过程是：

因为 start 是唯一的，所以先用 map 存储每一个 start 的对应下标。然后根据 start 的大小，对数组进行排序，方便二分查找。
最后，对于未排序数组中的每一个 end 值，分别在排序好的数组中，找到不小于 end[i] 的第一个元素。需要注意的是，找到的位置不能是 i 本身。

思路很朴素，但是二分查找的细节比较耗时，而且每次都花很长时间在扣边界上。等有时间看下别人的边界的写法。

class Solution {public int[] findRightInterval(int[][] arr) {int L = arr.length;HashMap<Integer, Integer> map = new HashMap<>();map.put(-1, -1);int[] end = new int[L];for (int i = 0; i < L; i++) {end[i] = arr[i][1];map.put(arr[i][0], i);}Arrays.sort(arr, Comparator.comparingInt(o -> o[0])); // start is uniqueint[] result = new int[L];for (int i = 0; i < L; i++) {result[i] = binarySearch(arr, end[i], 0, L - 1, i, map);}return result;}public int binarySearch(int[][] arr, int target, int L, int R, int i, HashMap<Integer, Integer> map) {if (arr[R][0] < target) return -1;// 只看(start,?)，找第一个start不小于target的位置while (L < R) {int M = L + ((R - L) >> 1);if (arr[M][0] == target) {return map.get(arr[M][0]);} else if (arr[M][0] < target) {L = M + 1;} else {// 保右端点if (R == M) return map.get(arr[M][0]);R = M;}}if (map.get(arr[L][0]) == i) L += 1; // 目标位置不能是i位置本身if (L >= arr.length) return -1;else return map.get(arr[L][0]);}
}