1.题目描述

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

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

返回一个由每个区间 i 的右侧区间的最小起始位置组成的数组。如果某个区间 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] 有最小的“右”起点。

2.思路

2.1 代码

需要在给定的数组 intervals 中找到右区间，其实就是在 intervals 中找到第一位大于等于当前行第二位的行号，那么题目就可以简化为在二维数组 intervals 的第一列中找到某一个数。

这么一看这道题目就简单了，首先需要维护第一列的数和对应行的关系，这里用一个 Info 类进行维护，index 表示所在行，value 表示数值。然后使用数组存放每一列构造出来的 Info 对象，再根据 Info 的 value 将数组从小到大进行排序。

完成排序后，使用二分查找法在该数组中依次对每一行的第二位进行查找，最后将查找到的 Info 对象的 index 存入结果数组中。代码如下：

class Solution {public int[] findRightInterval(int[][] intervals) {int[] ans = new int[intervals.length];if (intervals.length == 1) {ans[0] = -1;return ans;}Info[] list = new Info[intervals.length];for (int i = 0; i < intervals.length; i++) {Info info = new Info(i, intervals[i][0]);list[i] = info;}Arrays.sort(list, Comparator.comparingInt(o -> o.value));for (int i = 0; i < intervals.length; i++) {ans[i] = getRightArea(list, intervals[i][1]);}return ans;}public int getRightArea(Info[] list, int num) {if (num > list[list.length - 1].value) {return -1;}int left = 0;int right = list.length - 1;while (left < right) {int mid = (left + right) / 2;if (list[mid].value > num) {right = mid;} else if (list[mid].value < num) {left = mid + 1;} else {return list[mid].index;}}return list[left].index;}private class Info {int value;int index;public Info(int index, int value) {this.index = index;this.value = value;}}
}