这道题的核心是转换思路不要直接寻找“右区间”而是把所有区间的左端点抽出来排序问题就变成了二分查找。 题目理解给定一组区间每个区间的起点唯一。对每个区间 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){intnintervals.length;// starts[i] {原始起点, 原始下标}int[][]startsnewint[n][2];for(inti0;in;i){starts[i][0]intervals[i][0];starts[i][1]i;}Arrays.sort(starts,(a,b)-Integer.compare(a[0],b[0]));int[]ansnewint[n];for(inti0;in;i){inttargetintervals[i][1];// 当前区间的终点intleft0,rightn;// right 初始为 n方便统一处理“找不到”的情况while(leftright){intmidleft(right-left)/2;if(starts[mid][0]target){rightmid;// 尝试找更靠左的满足条件的起点}else{leftmid1;}}// left n 说明没有起点 targetans[i](leftn)?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){TreeMapInteger,IntegermapnewTreeMap();for(inti0;iintervals.length;i){map.put(intervals[i][0],i);// 起点 → 原始下标}int[]ansnewint[intervals.length];for(inti0;iintervals.length;i){Integerkeymap.ceilingKey(intervals[i][1]);// 最小的 end_i 的起点ans[i](keynull)?-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 写法更短但在面试中如果被追问底层红黑树也需要能答上来。
