寻找右区间如何用排序和二分查找？为什么只需要比较起点？

简化版

寻找右区间要求对每个区间 [start,end] 找到起点不小于 end 的区间中起点最小的那个。把所有区间起点连同原下标排序，然后对每个 end 做 lower_bound 二分即可。

详细版

右区间的定义只关心另一个区间的 start 是否 >= 当前 end，并不要求它和当前区间真实相邻，也不关心它的 end。因此可以预处理所有起点。排序数组元素为 (start,index)，对每个区间的 end 找第一个 start >= end 的位置，存在则返回对应原下标，否则返回 -1。

时间复杂度 O(n log n)，空间复杂度 O(n)。关键是保留原下标，因为排序会打乱区间顺序。

完整版教学

一、题目里的“右区间”到底是什么

对区间 i=[l,r]，右区间 j 需要满足：

start[j] >= r

并且在所有满足条件的区间里，start[j] 最小。注意它不是找“右边最近的下标”，而是找“起点最小但不小于当前终点”的区间。

当前 [2,3]
候选起点：3, 4, 10
最优右区间起点是 3

二、为什么只需要排序起点

右区间判断只用候选区间的起点，候选区间的终点不会参与比较。既然查询条件是“找第一个起点 >= end”，这就是典型 lower_bound。

信息	是否用于查询
候选区间 start	使用
候选区间 end	不使用
候选原下标	返回答案需要

记忆钩子：右区间不是比较两个完整区间，只是在所有 start 里找 end 的下界。

所以把起点拿出来排序就够了。

三、为什么必须保存原下标

排序后区间顺序会变化，但答案要求返回原数组中的下标。如果只保存起点，二分找到后不知道对应哪个原区间。

intervals = [[3,4], [2,3], [1,2]]
排序起点后：[(1,2), (2,1), (3,0)]

对 [2,3] 的 end=3，二分找到 (3,0)，返回原下标 0。

四、二分查找怎么写

对排好序的 starts 数组找第一个 start >= target：

left = 0, right = n
while left < right:
    mid = (left + right) / 2
    if starts[mid].start >= target:
        right = mid
    else:
        left = mid + 1

循环结束时，left 就是第一个满足条件的位置。如果 left == n，说明没有右区间。

五、代码模板

int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    int[][] starts = new int[n][2];
    for (int i = 0; i < n; i++) {
        starts[i][0] = intervals[i][0];
        starts[i][1] = i;
    }
    Arrays.sort(starts, Comparator.comparingInt(a -> a[0]));
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        int target = intervals[i][1];
        int l = 0, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (starts[m][0] >= target) r = m;
            else l = m + 1;
        }
        ans[i] = l == n ? -1 : starts[l][1];
    }
    return ans;
}

这里二分右边界设成 n，方便表达“找不到”的情况。

六、用例子推演

intervals=[[1,2],[2,3],[3,4]]：

starts = [(1,0), (2,1), (3,2)]
区间 [1,2] 查 target=2 => 返回 1
区间 [2,3] 查 target=3 => 返回 2
区间 [3,4] 查 target=4 => 找不到，返回 -1

答案是 [1,2,-1]。

七、常见误区与追问

误区：按区间终点排序后查找。 查询条件是候选起点，不是候选终点。
误区：返回排序后的下标。 题目要原数组下标，排序时必须保存 index。
误区：找 start > end。 右区间允许 start == end。
追问：能不能用 TreeMap？ 可以，把 start -> index 放进 TreeMap，用 ceilingEntry(end)。
追问：如果起点不唯一怎么办？ 原题常约束起点唯一；不唯一时要明确返回哪个下标。
追问：复杂度是多少？ 排序 O(n log n)，每个区间二分 O(log n)。

八、加强记忆

寻找右区间就是“在所有起点里找当前终点的下界”。排序起点，保留原下标，对每个 end 做 lower_bound。别被“区间”两个字吓到，这题真正比较的只有 start；也别忘了 start == end 是合法右区间。

简化版

详细版