0436. Find Right Interval
=========================
题目信息
--------
:题号: 0436
:难度: Medium
:主题: 区间、唯一开始点、右侧候选、原下标
:原题: `LeetCode 0436 `_
:重点: 对每个区间寻找 ``start_j >= end_i`` 的最小开始点、返回原数组下标、无候选时返回 ``-1``
题目重述
--------
给定区间数组 ``intervals``,每个区间 ``i`` 表示为 ``[start_i, end_i]``,并保证所有 ``start_i`` 互不相同。对每个区间寻找它的右区间 ``j``:要求 ``start_j >= end_i``,并且在所有满足条件的区间中,``start_j`` 最小。
返回长度与输入相同的数组 ``answer``,其中 ``answer[i]`` 是右区间在原数组中的零基下标;若不存在满足条件的区间,则为 ``-1``。``intervals.length`` 位于 ``[1, 2 * 10^4]``,端点位于 ``[-10^6, 10^6]``,且每个区间满足 ``start_i <= end_i``。
自建示例
--------
三个区间互相形成右侧关系:
.. code-block:: text
输入:intervals = [[3,4], [1,2], [2,3]]
输出:[-1, 2, 0]
解释:[3,4] 没有开始点至少为 4 的区间;[1,2] 的最小合格开始点是 2,位于下标 2;[2,3] 的右区间开始点为 3,位于下标 0。
区间可以把自己作为右区间:
.. code-block:: text
输入:intervals = [[5,5]]
输出:[0]
解释:该区间的开始点 5 大于或等于自身结束点 5,因此原下标 0 满足定义。
对开始点排序后做 lower_bound
------------------------------
右区间只由开始点决定。把所有 ``(start, 原下标)`` 按开始点升序保存,对每个 ``end_i`` 二分查找第一个大于等于它的开始点;这一定是满足条件者中开始点最小的一个,直接返回其原下标。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector findRightInterval(
std::vector>& intervals) {
std::vector> starts;
for (int i = 0; i < static_cast(intervals.size()); ++i) {
starts.push_back({intervals[i][0], i});
}
std::sort(starts.begin(), starts.end());
std::vector result;
for (const auto& interval : intervals) {
auto it = std::lower_bound(
starts.begin(), starts.end(),
std::make_pair(interval[1], -1));
result.push_back(it == starts.end() ? -1 : it->second);
}
return result;
}
};
代码分析
--------
开始点互不相同,所以 lower_bound 找到的候选唯一;保存原下标避免排序后丢失答案位置。预处理排序为 ``O(n log n)``,每个区间二分查询同为 ``O(log n)``,总体时间 ``O(n log n)``,额外空间为 ``O(n)``。