0%

[Leetcode]436. Find Right Interval (C++)

题目描述

题目链接:436. Find Right Interval

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

例子

例子 1

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

例子 2

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied “right” interval for [3,4].
For [2,3], the interval [3,4] has minimum-“right” start point;
For [1,2], the interval [2,3] has minimum-“right” start point.

例子 3

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied “right” interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-“right” start point.

解题思路

通常来说这一类涉及一堆区间的数组,我们都是通过对其进行按起始点排序,然后前后比较获得结果这个思路。但是这道题要求我们返回的是对于每个区间,找出另一个区间的起始点最接近当前区间结束点的索引,所以如果直接排序会失去原有的索引信息。基于这一点我们需要对其索引进行存储,所以可以用哈希表来以每个区间的起始点作为键值来存储对应的索引。接下来对区间排序。排序后对每一个区间,在数组中进行一次二分查找找出第一个起始点比该区间末尾点的区间,然后在结果中存入对应索引值即可。如果找不到则存入 -1

以上是解题思路,具体实现的时候我们可以借助 std::mapstd::lower_bound 这两个工具。使用 std::map 而非 std::unordered_map 的原因是前者可以同时完成存储索引和对区间起始点排序的功能;而在之后对每个区间寻找符合要求区间时,我们只需要对该 map 使用 lower_bound 即可。lower_bound() 可以返回第一个大于或等于 我们给的阈值 val 的元素,正是我们这里需要的。代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <map>

class Solution {
public:
std::vector<int> findRightInterval(std::vector<std::vector<int>>& intervals) {
std::map<int, int> start_index; // start point -> index
for (int i = 0; i < intervals.size(); i++) {
start_index[intervals[i][0]] = i;
}

std::vector<int> result(intervals.size(), -1);
for (int i = 0; i < intervals.size(); i++) {
int start_point = intervals[i][0];
int end_point = intervals[i][1];
auto bound = start_index.lower_bound(end_point);
if (bound != start_index.end()) {
result[start_index[start_point]] = bound->second;
}
}

return result;
}
};
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(n)