LeetCode 436. 寻找右区间

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 排序 二分查找

题目描述

✅ 436. 寻找右区间

image-20260929100701914

image-20260929100702013

题意分析

对每个原区间 i，寻找满足 start[j] >= end[i] 的区间，并在其中选择起点最小的一个，返回它的原始下标；若没有这样的区间，返回 -1。

题目保证所有起点不同，因此最小合法起点确定后，对应区间也唯一。条件包含等号，刚好与当前终点相接也算合法；若当前区间起点等于终点，它自己也能成为答案。

解法：起点排序 + 二分

核心思路

[!blue]

判断一个候选是否符合要求，只需要它的起点。先将 (起点, 原下标) 绑定后按起点升序排序，那么对当前终点 end，候选起点会分成“小于 end”和“大于等于 end”两段。第二段的第一个位置，就是满足条件的最小起点。

用半开区间 [l,r) 保存尚未确定的部分，初始为 [0,n)。维护两个边界事实：l 左侧的起点都小于 end，从 r 开始的起点都大于等于 end；初始两侧都为空，自然成立。

若中点起点已经大于等于 end，由于排序，其右侧也都合格，令 r = mid，继续检查是否还有更早的合格位置。否则中点及左侧全部不合格，令 l = mid+1。每次都缩短尚未确定的区间，直到 l == r，这个分界位置就是第一个合格起点。

分界可能等于 n，表示所有起点都小于当前终点，此时没有右区间；否则从数对中取出原下标。排序后的下标只表示起点的排名，不能直接作为答案。原 intervals 不参与排序，所以逐项查询并写入 res[i] 后，结果仍对应输入顺序。

解题步骤

  1. 为每个区间建立 (start,i) 数对，按 start 升序排序。
  2. 按原顺序遍历区间，取它的 end 作为本次二分目标，并重置 l = 0、r = n。
  3. 比较中点起点与 end，按上述规则寻找第一个大于等于目标的位置。
  4. 若最终位置是 n，写入 -1；否则写入该数对保存的原下标。

不要在二分时排除当前区间。长度为零的区间满足 start == end，在起点互不相同的条件下，它自己就是最小的合法候选。

代码实现

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] pairs = new int[n][2];

        for (int i = 0; i < n; i++) {
            pairs[i][0] = intervals[i][0];
            // 排序前保存原下标，二分位置本身不是最终答案。
            pairs[i][1] = i;
        }

        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));

        int[] res = new int[n];

        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int l = 0;
            int r = n;

            while (l < r) {
                int mid = l + (r - l) / 2;

                // 满足条件时继续向左找，保留当前中点作为分界候选。
                if (pairs[mid][0] >= end) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }

            if (l == n) {
                res[i] = -1;
            } else {
                res[i] = pairs[l][1];
            }
        }

        return res;
    }
}

import "sort"

func findRightInterval(intervals [][]int) []int {
    n := len(intervals)
    pairs := make([][]int, n)
    for i := 0; i < n; i++ {
        // 排序前保存原下标，二分位置本身不是最终答案。
        pairs[i] = []int{
            intervals[i][0],
            i,
        }
    }
    sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] })

    res := make([]int, n)
    for i := 0; i < n; i++ {
        end := intervals[i][1]
        l, r := 0, n
        for l < r {
            mid := l + (r-l)/2
            // 满足条件时继续向左找，保留当前中点作为分界候选。
            if pairs[mid][0] >= end {
                r = mid
            } else {
                l = mid + 1
            }
        }
        if l == n {
            res[i] = -1
        } else {
            res[i] = pairs[l][1]
        }
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n\log(n+1))$，排序一次，并对每个区间进行一次对数时间的下界查找。
  • 空间复杂度：不计返回结果为 $O(n)$，用于起点与原下标数对；结果数组另占 $O(n)$。

关键点总结

[!green]

  • 查询条件含等号，相接区间也符合要求。
  • 排序位置不是答案，必须还原原始下标。
  • 候选只需比较起点，不需要其终点。

易错点总结

[!yellow]

  • 只排序起点而不保存原下标：无法正确返回输入位置。
  • 用当前起点作为查询目标：没有满足右区间的定义。
  • 精确匹配失败就返回 -1：更大的起点仍可能是答案。
  • 强行排除自身：点区间可能以自身为合法最小候选。

相似题目

题目 难度 关联与区别
35. 搜索插入位置 简单 按区间起点排序后，查询第一个起点不小于当前终点的位置，就是下界二分。
729. 我的日程安排表 I 中等 同样需要按起点寻找前驱后继，日程题再检查是否重叠，本题直接返回符合右侧条件的索引。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/21981661
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！