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; }    }}

2.2 测试结果

通过测试

3.总结

• 使用 Info 类维护第一列和行的关系，并按照值进行排序
• 使用二分查找法对第二列的数进行查找