题目描述

给你一个数组 intervals，intervals[i] = [start_i, end_i]，且每一个 start_i 都是 不同的。

区间 i 的 右区间 是另一个区间 j，满足 start_j >= end_i 且 start_j 是 最小的。

返回一个数组，包含每一个区间 i 的 右区间 下标。如果区间 i 的 右区间 不存在，则在下标 i 的位置放入 -1。

样例

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

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

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

限制

• 1 <= intervals.length <= 2 * 10^4
• intervals[i].length == 2
• -10^6 <= starti <= endi <= 10^6
• 每个区间的起始下标都是 不同的。

算法

(排序，二分) $O(n \log n)$

1. 将区间按照起始点从小到大排序。
2. 遍历区间，对于每个区间 $i$，二分查找区间 $j$，满足 start_j >= start_i 且 start_j 最小。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 对于每个区间二分查找，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序前的下标以及答案。

C++ 代码

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        const int n = intervals.size();
        for (int i = 0; i < n; i++)
            intervals[i].push_back(i);

        sort(intervals.begin(), intervals.end());

        vector<int> ans(n, -1);
        for (int i = 0; i < n; i++) {
            int l = i + 1, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (intervals[mid][0] < intervals[i][1])
                    l = mid + 1;
                else
                    r = mid;

            }
            if (l < n)
                ans[intervals[i][2]] = intervals[l][2];
        }
        return ans;
    }
};