Skip to content
436. 寻找右区间
<![CDATA[
class Solution {
public int[] findRightInterval(int[][] intervals) {
int N = intervals.length;
// 将原数组拷贝进新数组，且新数组用额外一个元素来储存下标
for(int i = 0; i<N; i++){
intervals[i] = new int[]{intervals[i][0], intervals[i][1], i};
}
// 按照左端点（行）排序, 记住：
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
// deepToString可以用来print多维数组
System.out.println(Arrays.deepToString(intervals));
// 创建res 数组来存储结果，注意结果为对应下标
int[] res= new int[N];
// 初始化为负一因为当不存在右区间时结果为-1
Arrays.fill(res,-1);
// 枚举每一个区间
for(int i = 0; i<N; i++){
// 二分查找看枚举的区间是否有右区间
int l = 0, r = N-1;
while(l<r){
int mid = l+r>>1;
// 若左端点大于暂时目标的右端点，说明目标在左侧
// 目标就是intervals[i][1]也就是最小的右区间
if(intervals[mid][0]>=intervals[i][1]) r = mid;
else l = mid + 1;
}
System.out.println(r);
// 若找到的目标的左端点大于枚举目标的右端点，则说明右区间存在
// 将对应的下标存入原本区间所在的位置
if(intervals[r][0]>=intervals[i][1]) res[intervals[i][2]] = intervals[r][2];
}
return res;
}
}
]]>
