436. 寻找右区间

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

需要我这个语文课代表翻译一下今天的题目。

题目给了一个数组 intervals，其中的每个元素都是一个区间，区间的两个值分别是起点和终点。

当区间 B 的起点 大于等于 区间 A 的终点，我们就说区间 B 在区间 A 的右侧。

让我们求每个区间的右侧第一个区间（所有右侧的区间中，起点最小的那个）。

如果还不好理解，请看下面两张图。(为了防止区间的线段相互覆盖，我把区间向上平移了一点)

示例二 intervals = [[3,4],[2,3],[1,2]]

实例三 intervals = [[1,4],[2,3],[3,4]]

解题方法

分析

右侧区间，其起点 大于等于 当前区间终点 。

右侧第一个区间，就是找右侧区间中 最小的那个。

题目已经说了每个区间的起点 都不会重复。

首先，我们可以把所有区间的起点 取出来，这样就成了一个起点的数组 。

当我们想要寻找一个区间 右边的第一个区间时，其实就是求 内 大于等于 的最小值。

怎么找到数组中大于等于 的最小值的呢？

最粗暴的方法是遍历，遍历一次的时间复杂度是 。

对于数组中的每个区间都要遍历一遍，因此总时间复杂度是 。题目给出的数据规模是 ，会超时。

怎么办？

可以使用「二分查找」。

二分查找

二分查找有不同的应用：

1. 找到 的位置（常见）
2. 找到大于等于 的第一个位置
3. 找到大于 的第一个位置
4. 找到小于等于 的第一个位置
5. 找到小于 的第一个位置

今天使用的就是第 2 种应用：「找到大于等于 的第一个位置」。

二分查找的本质是每次排除掉不可能存在结果的区间。

下面详细说明，如何在有序数组中，找到大于等于 的第一个位置。

首先，我们定义 指向数组的开始，定义 指向数组的结束，即当前搜索的空间是 双闭区间。

令 ，即指向区间的中间位置。

每次判断 与 的大小：

1. 如果 。

说明 以及其左边的所有元素都不是「大于等于 的数字」。

因此令 。

为什么需要 + 1？因为 不符合要求，因此不在下次的搜索空间中

1. 如果 ，即 是大于等于 的位置。

说明 右边（不含 ）的所有元素都不是「第一个大于等于 的数字」。

因此令 。

为什么不需要 + 1？因为 有可能是结果，因此需要在下次的搜索空间中

举例。

代码

使用二分查找，找到区间右侧的第一个区间的起点。

然后我们通过字典（哈希表）再找到这个起点对应的区间的下标。

代码如下：

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        start_map = {interval[0] : i for i, interval in enumerate(intervals)}
        start_list = [interval[0] for interval in intervals]
        res = []
        start_list.sort()
        for interval in intervals:
            pos = self.higher_find(start_list, interval[1])
            res.append(start_map[start_list[pos]] if pos != -1 else -1)
        return res
    def higher_find(self, nums, target):
        left, right = 0, len(nums) - 1
        # [left, right]
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1
        if left >= len(nums) or nums[left] < target:
            return -1
        return left

总结

1. 今天主要是题目很难理解；
2. 二分查找的变形，也需要掌握，重点是理解。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。