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

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

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

示例 1：

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

示例 2：

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

示例 3：

输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

提示：

• 1 <= intervals.length <= 2 * 10^4
• intervals[i].length == 2
• -106 <= starti <= endi <= 10^6
• 每个间隔的起点都 不相同

思路

• 题目描述的有些看不懂，就是找个有区间，使其与当前区间有交集。看例2， [1, 2] 与 [3, 4] 没有交集， 与 [2, 3] 有交集，假如再有个[1, 3] ，其与[1, 2] 也是有交集的，但是 2 - 2 = 0 < 2- 1 = 1。题目说最小的右起点，所以取[1, 2] 而不是 [1, 3]
• 看提示条件，数组的长度很大，所以我们不能一个个去查找比较，这样肯定会超时的。如何缩短，二分法，但是我们知道，数组有顺序的，才能使用二分法，题目是无序的，所以我们需要对二位数组排序，但是排序索引就乱了，所以我们需要保存下二维数组的索引
• 定义一个int[][] startIntervals = new int[n][2] 的数组，n是intervals数组的长度，我们需要两个值， startIntervals[i][0] ，存储intervals数组的start值，startIntervals[i][1] 存储当前区间的索引

二分法

 /**
     * 二分法
     * @param intervals
     * @return
     */
    public static int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] startIntervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            startIntervals[i][0] = intervals[i][0];
            startIntervals[i][1] = i;
        }
        int[] ans = new int[n];
        // 根据start进行排序，然后使用二人分法
        Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int left = 0, right = n - 1, index = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (startIntervals[mid][0] >= end) {
                    index = startIntervals[mid][1];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = index;
        }
        return ans;
    }