寻找右区间

标签: 数组 二分查找 排序

难度: Medium

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。

区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。注意 i 可能等于 j 。

返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

 

示例 1：

输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

示例 2：

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

示例 3：

输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

提示：

  • 1 <= intervals.length <= 2 * 104
  • intervals[i].length == 2
  • -106 <= starti <= endi <= 106
  • 每个间隔的起点都 不相同

Submission

运行时间: 67 ms

内存: 20.4 MB

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        for i, interval in enumerate(intervals):
            interval.append(i)
        intervals.sort()

        n = len(intervals)
        ans = [-1] * n

        for _, end, idx in intervals:
            i = bisect_left(intervals, [end])
            if i < n:
                ans[idx] = intervals[i][2]
        return ans

Explain

这个题解的思路是先给每个区间添加原始下标，然后对区间按照起点排序。接着遍历排序后的区间，对于每个区间，用二分查找在排序后的区间中寻找起点大于等于当前区间终点的最小区间，如果找到就将对应下标赋值给结果数组对应位置，找不到就保持-1不变。最后返回结果数组。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        # 给每个区间添加原始下标
        for i, interval in enumerate(intervals):
            interval.append(i)
        # 按照起点对区间排序
        intervals.sort()

        n = len(intervals)
        ans = [-1] * n

        # 遍历排序后的区间
        for _, end, idx in intervals:
            # 在排序后的区间中二分查找起点大于等于当前区间终点的最小区间
            i = bisect_left(intervals, [end])
            if i < n:
                ans[idx] = intervals[i][2]
        return ans

Explore

在解题思路中先给每个区间添加原始下标是为了在对区间按起点排序后，仍能够追踪每个区间在原始数组中的位置。这一步是必要的，因为排序会改变区间的顺序，而最终需要按照原始顺序输出每个区间的正确的右区间下标。通过添加原始下标，即使区间顺序改变，我们也能准确地将查找到的右区间的下标放在结果数组的正确位置。

在使用二分查找时，通过查找不小于当前区间终点的最小起点，确保找到的是起点大于等于当前区间终点的最小区间。具体实现是利用`bisect_left`函数，它查找到的是数组中第一个不小于目标值（当前区间的终点）的元素位置。由于区间已经按起点排序，这保证了找到的是所有满足条件的起点中最小的一个。

在二分查找过程中，如果没有找到符合条件的区间，意味着所有的区间起点都小于当前区间的终点或者查找的结果超出了区间数组的范围。在这种情况下，`bisect_left`返回的索引值会等于区间的长度（n），这个值在数组索引范围之外。因此，没有合适的区间可用作右区间。在这种情况下，结果数组的对应位置会保持初始值-1，表示没有找到合适的右区间。

在使用`bisect_left(intervals, [end])`进行查找时，这里的`[end]`作为查找参数是足够的，因为`bisect_left`仅基于区间数组中元素的第一个元素（即起点）来进行比较。由于区间已按起点排序，传入单个元素列表`[end]`将使得`bisect_left`找到第一个起点不小于`end`的区间。这种查找方式利用了Python元组和列表的比较规则，即首先比较第一个元素，如果相等再比较下一个元素，所以这里仅提供起点即可正确工作。