题目

难度：★★★☆☆
类型：数组
方法：二分法

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。

对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。
如果区间 j 不存在，则将区间 i 存储为 -1。
最后，你需要输出一个值为存储的区间值的数组。

注意:

你可以假设区间的终点总是大于它的起始点。
你可以假定这些区间都不具有相同的起始点。

示例

示例 1:

输入: [ [1,2] ]
输出: [-1]

解释:集合中只有一个区间，所以输出-1。

示例 2:

输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]

解释:对于[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]具有最小的“右”起点;
对于[1,2]，区间[2,3]具有最小的“右”起点。

示例 3:

输入: [ [1,4], [2,3], [3,4] ]
输出: [-1, 2, -1]

解释:对于区间[1,4]和[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]有最小的“右”起点。

解答

这个题说的有点含蓄，先来翻译一下：给出一个包含若干区间的数组，对于其中的每个区间，请找到数组中在该区间右边的区间中，与该区间最相近的一个，并返回其下标，如果找不到，则返回-1。因为要对每个区间都要计算，因此最后返回的是个下标数组。

我们可以用二分法解决这个问题，依然需要对所有区间按照起点排序。

这里为了便于表示，定义了一个很简单的类Interval，表示一个区间，包含该区间起点终点和对应下标三个实例变量。

我们写了seek方法，用于寻找某一个区间的最相近的右区间，其中主要部分是用二分法搜索得到的，这里需要大家注意搜索的条件。

class Interval:
    def __init__(self, min, max, id):
        self.id = id
        self.min = min
        self.max = max


class Solution:
    def findRightInterval(self, intervals):
        n = len(intervals)
        intervals = [Interval(min, max, id) for id, (min, max) in enumerate(intervals)]
        intervals.sort(key=lambda x: x.min)
        res = [-1 for _ in range(n)]

        def seek(i):
            l, r = i, n - 1
            if intervals[r].min < intervals[l].max:
                return -1
            while l < r:
                m = (l + r) // 2
                if intervals[m].min >= intervals[i].max:
                    r = m
                else:
                    l = m + 1
            return r

        for i in range(n):
            r = seek(i)
            if r >= 0:
                res[intervals[i].id] = intervals[r].id

        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析