原文链接: https://leetcode-cn.com/problems/find-right-interval

英文原文

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

 

Example 1:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

 

Constraints:

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -106 <= starti <= endi <= 106
• The start point of each interval is unique.

中文题目

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

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

返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 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
• 每个间隔的起点都 不相同

通过代码

官方题解

方法一：暴力法

算法：

最简单的解决方案是对于集合中的每个区间，我们扫描所有区间找到其起点大于当前区间的终点的区间（具有最先差值）。在扫描的过程中，我们跟踪满足给定条件区间的索引。每个区间的结果存储在 res 数组中。

[solution1-Java]
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[] res = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            int min = Integer.MAX_VALUE;
            int minindex = -1;
            for (int j = 0; j < intervals.length; j++) {
                if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < min) {
                    min = intervals[j][0];
                    minindex = j;
                }
            }
            res[i] = minindex;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n^2)$。找到每个区间的答案需要扫描整个区间集合。
• 空间复杂度：$\mathcal{O}(n)$，数组 $\text{res}$ 具有 $n$ 个元素。

方法二：排序 + 扫描

算法：

我们使用一个哈希表 $\text{hash}$，存储的数据形式的键值对。在这里，$\text{Key}$ 对应区间，而 $\text{Value}$ 对应在 $\text{intervals}$ 数组中特定区间的索引。我们将 $\text{intervals}$ 中的每个元素存储在哈希表中。

我们根据区间的起点对 $\text{intervals}$ 数组进行排序。我们需要将数组的索引存储在哈希表中，以便排序后也能获得对应的索引。

然后，依次遍历数组中的区间，并找到在该区间结束位置后的一个区间。怎么找？由于 $\text{intervals}$ 数组是基于起点排序的，并且对于给定的区间，结束点总是大于起始点。因此我们只需要使用索引 $j$ 搜索区间，$i+1< j < n$，这样按升序扫描时遇到第一个区间就是所需的结果。

然后，我们可以在哈希表中获取该区间对应的索引，将该索引存储到 $res$ 数组中。

[solution2-Java]
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[] res = new int[intervals.length];
        Map<int[], Integer> hash = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            hash.put(intervals[i], i);
        }
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for (int i = 0; i < intervals.length; i++) {
            int min = Integer.MAX_VALUE;
            int minindex = -1;
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < min) {
                    min = intervals[j][0];
                    minindex = hash.get(intervals[j]);
                }
            }
            res[hash.get(intervals[i])] = minindex;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$。
  • 排序使用了 $O\big(nlog(n)\big)$ 的时间。
  • 对于第一个区间，我们需要在 $n-1$ 个元素中搜索。
  • 对于第二个元素，我们需要在 $n-2$ 个元素中搜索，等等总共是 $(n-1) + (n-2) + … + 1 = \frac{n.(n-1)}{2} = O(n^2)$。
• 空间复杂度：$O(n)$，$\text{res}$ 和 $\text{hash}$ 均存储了 $n$ 个元素。

方法三：排序 + 二分查找

算法：

我们可以在一定程度上优化上述方法，因为 $\text{intervals}$ 有序，则我们不必用线性的方法来搜索所需的区间，而是可以利用二分查找来找到我们所需的区间。

如果找到所需的区间，则从哈希表中获取对用的所有添加到 $\text{res}$ 中，反之则添加 $\text{-1}$。

复杂度分析

• 时间复杂度：$O\big((n.log(n)\big)$。排序花费了 $O\big(n.log(n)\big)$ 的时间，二分查找花费了 $O\big(log(n)\big)$ 的时间。
• 空间复杂度：$O(n)$，$\text{res}$ 和 $\text{hash}$ 均存储了 $n$ 个元素。

方法四：使用 TreeMap

算法：

在该方法中，我们不使用 hashmap，而是使用 TreeMap，底层是由红黑树（一种平衡的二叉搜索树）实现的。TreeMap 以 $\text{(Key, Value)}$ 的形式存储数据，并始终根据键值排序。这样我们将数组中的区间存储到 TreeMap 中，这样就可以获得排序的序列。

现在，我们遍历 $\text{intervals}$ 中的每个区间，并使用函数 TreeMap.ceilingEntry(end_point)，若 $\text{Key}$ 刚刚好大于所选区间 $\text{end_point}$，则 返回 Key。反之，返回 null。

如果是非空值返回，则我们从 $\text{(Key, Value)}$ 对中获得 $\text{Value}$。然后添加到 $res$ 数组中。反之添加 $\text{-1}$ 到 $res$ 数组中。

复杂度分析

• 时间复杂度：$O\big(N \cdot \log{N}\big)$。TreeMap 的插入操作需要 $O\big(\log{N}\big)$ 的时间。TreeMap 的 ceilingEntry 操作需要 $O\big(\log{N}\big)$ 的时间。
• 空间复杂度：$O(n)$，$\text{res}$ 和 $\text{hash}$ 均存储了 $n$ 个元素。

方法五：使用两个数组

算法：

我们保持两个数组：

1. $\text{intervals}$，基于起始点排序。
2. $\text{endIntervals}$，基于结束点排序

我们从 $\text{endIntervals}$ 数组中取出 $i^{th}$ 个区间，就可以从左到右扫描 $\text{intervals}$ 数组中的区间来找到满足右区间条件的区间。因为 $\text{intervals}$ 是基于起始点排序的。比如，从 $\text{intervals}$ 数组中选择的区间索引是 $j$。

现在，当我们从 $\text{endIntervals}$ 数组中获取下一个区间时（即 $(i+1)^{th}$ 个区间），我们不需要从第一个索引开始扫描 $\text{intervals}$ 数组。相反，我们可以直接从 $j^{th}$ 索引开始，上一次搜索在 $\text{intervals}$ 数组中停止在这个索引。

我们还是用了 hashmap $\text{hash}$ 保留了最初的区间和索引对应关系。

我们通过看图来了解该算法是如何工作的：

<,,,,,,,,,,,,,,,>

复杂度分析

• 时间复杂度：$O\big(N \cdot \log{N}\big)$。排序花费了 $O\big(N \cdot \log{N}\big)$ 的时间。
• 空间复杂度：$O(n)$，$\text{intervals}$，$\text{endIntervals}$，$\text{res}$ 和 $\text{hash}$ 均存储了 $n$ 个元素。

统计信息

通过次数	提交次数	AC比率
9530	19466	49.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
将数据流变为多个不相交区间	困难