这道题的核心是转换思路：不要直接寻找“右区间”，而是把所有区间的左端点抽出来排序，问题就变成了二分查找。

📝 题目理解

给定一组区间，每个区间的起点唯一。对每个区间 i，需要找到另一个区间 j，满足 start_j >= end_i，且 start_j 最小。返回所有 j 的下标；如果不存在，返回 -1。注意 i 可以等于 j。

解法一：排序 + 二分查找（推荐）

核心思路：把所有区间的起点和原始下标存成一个新数组，按起点升序排序。然后遍历原区间，对每个区间的终点 end_i，在排序后的起点数组中用二分查找找到第一个 >= end_i 的起点。它对应的原始下标就是答案；如果找不到，就是 -1。

importjava.util.Arrays;classSolution{publicint[]findRightInterval(int[][]intervals){intn=intervals.length;// starts[i] = {原始起点, 原始下标}int[][]starts=newint[n][2];for(inti=0;i<n;i++){starts[i][0]=intervals[i][0];starts[i][1]=i;}Arrays.sort(starts,(a,b)->Integer.compare(a[0],b[0]));int[]ans=newint[n];for(inti=0;i<n;i++){inttarget=intervals[i][1];// 当前区间的终点intleft=0,right=n;// right 初始为 n，方便统一处理“找不到”的情况while(left<right){intmid=left+(right-left)/2;if(starts[mid][0]>=target){right=mid;// 尝试找更靠左的满足条件的起点}else{left=mid+1;}}// left == n 说明没有起点 >= targetans[i]=(left<n)?starts[left][1]:-1;}returnans;}}

关键点：二分结束时 left 是第一个满足 starts[left][0] >= target 的位置。如果 left == n，说明所有起点都小于 target，即不存在右区间。

解法二：TreeMap（更简洁）

因为起点唯一，且需要找大于等于某值的最小键，TreeMap 的 ceilingKey / ceilingEntry 天然适合这个场景。

importjava.util.TreeMap;classSolution{publicint[]findRightInterval(int[][]intervals){TreeMap<Integer,Integer>map=newTreeMap<>();for(inti=0;i<intervals.length;i++){map.put(intervals[i][0],i);// 起点 → 原始下标}int[]ans=newint[intervals.length];for(inti=0;i<intervals.length;i++){Integerkey=map.ceilingKey(intervals[i][1]);// 最小的 >= end_i 的起点ans[i]=(key==null)?-1:map.get(key);}returnans;}}

⚠️ 排序比较器的小坑

排序时建议用 Integer.compare(a[0], b[0])，不要用 a[0] - b[0]。本题起点范围到 -10^6，虽然相减不会溢出 int，但用 Integer.compare 是更稳妥的写法。

📊 复杂度对比

方法 时间复杂度 空间复杂度
排序 + 二分 O(n log n)（排序 + n次二分） O(n)
TreeMap O(n log n)（n次插入 + n次查找） O(n)

两种方法在复杂度上等价。如果面试中只写一种，优先推荐“排序 + 二分查找”，因为它更通用，且不依赖特定数据结构，更能体现对二分边界的掌控能力。TreeMap 写法更短，但在面试中如果被追问底层（红黑树）也需要能答上来。