友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
436. 寻找右区间
给你一个区间数组 intervals，其中 intervals[i] = [starti, endi]，且每个 starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。注意 i 可能等于 j 。
返回一个由每个区间 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 * 104 -
intervals[i].length == 2 -
-106 <= starti <= endi <= 106 -
每个间隔的起点都 不相同
思路分析
排序+二分查找。由于左端点都不同，可以根据左端点的值来来对区间进行排序。然后在这个有序序列中，查找右端点的“最近左端点”。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-16 16:16:17
*/
public int[] findRightInterval(int[][] intervals) {
int length = intervals.length;
Integer[] index = new Integer[length];
for (int i = 0; i < length; i++) {
index[i] = i;
}
Arrays.sort(index, Comparator.comparingInt((Integer a) -> intervals[a][0]));
int[] result = new int[length];
for (int i = 0; i < length; i++) {
int target = intervals[i][1];
int left = 0, right = length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int start = intervals[index[mid]][0];
if (start >= target) {
right = mid;
} else {
left = mid + 1;
}
}
result[i] = target <= intervals[index[left]][0] ? index[left] : -1;
}
return result;
}