寻找右区间 图解题解

这道题到底在问什么

输入

intervals=[[3,4],[2,3],[1,2]]

输出

[-1,0,1]

输入

intervals=[[1,4],[2,3],[3,4]]

输出

[-1,2,-1]

最优解：一步一步想明白

1. 3记住三步:① 起点带原下标一起排序;② 对每个区间的终点 end,二分找第一个 ≥ end 的起点(所在区间);③ 用原下标映射回答案。下面每帧都在套它。
2. 4先把四个区间的起点单独拎出来:1、3、2、5，它们的原区间编号依次是 0、1、2、3。直接二分需要有序,所以下一步排序;但排序会打乱顺序,必须把「原区间编号」绑在每个起点身上一起搬。
3. 5排序完成,起点升序排好:1、2、3、5。看右边侧栏,这是全篇的关键账本:排序下标 0 到 3 分别对应原区间 0、2、1、3。二分会在这个有序数组上定位,定位后再查账本换回原区间编号。
4. 6现在处理 区间 0=[1, 2]。它的右侧区间,就是「起点 ≥ 它的终点 2」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 2 的起点。
5. 7搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它 ≥ 终点 2，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。
6. 8把起点 3 记成新的、更靠左的候选(绿色移到下标 2),只把它右边灰掉。接着到它左边找有没有更小、也合格的起点。
7. 9搜索窗口 [0, 2) 的正中间是下标 1，起点 2。它 ≥ 终点 2，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。绿色那格是目前记下的候选。
8. 10把起点 2 记成新的、更靠左的候选(绿色移到下标 1),只把它右边灰掉。接着到它左边找有没有更小、也合格的起点。
9. 11搜索窗口 [0, 1) 的正中间是下标 0，起点 1。它比终点 2 小,接不住这个终点,它和它左边都排除掉,到右边继续找。绿色那格是目前记下的候选。
10. 12起点 1 比终点 2 小,把 mid 及它左边整段灰掉,l 收到 1。窗口收空,保留的候选下标 1 就是位置。
11. 13二分结束,l 停在下标 1(起点 2 ≥ 终点 2)。注意答案要的是「原区间编号」,查侧栏面板:排序下标 1 对应原区间 2，所以 区间 0=[1, 2] 的答案是 2。
12. 14现在处理 区间 1=[3, 4]。它的右侧区间,就是「起点 ≥ 它的终点 4」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 4 的起点。
13. 15搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它比终点 4 小,接不住这个终点,它和它左边都排除掉,到右边继续找。
14. 16起点 3 比终点 4 小,把 mid 及它左边整段灰掉,l 收到 3。继续往右找第一个够大的起点。
15. 17搜索窗口 [3, 4) 的正中间是下标 3，起点 5。它 ≥ 终点 4，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。
16. 18把起点 5 记成新的、更靠左的候选(绿色移到下标 3),只把它右边灰掉。此时窗口 [3, 3) 收空,保留的候选下标 3 就是要找的位置。
17. 19二分结束,l 停在下标 3(起点 5 ≥ 终点 4)。注意答案要的是「原区间编号」,查侧栏面板:排序下标 3 对应原区间 3，所以 区间 1=[3, 4] 的答案是 3。
18. 20现在处理 区间 2=[2, 3]。它的右侧区间,就是「起点 ≥ 它的终点 3」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 3 的起点。
19. 21搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它 ≥ 终点 3，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。
20. 22把起点 3 记成新的、更靠左的候选(绿色移到下标 2),只把它右边灰掉。接着到它左边找有没有更小、也合格的起点。
21. 23搜索窗口 [0, 2) 的正中间是下标 1，起点 2。它比终点 3 小,接不住这个终点,它和它左边都排除掉,到右边继续找。绿色那格是目前记下的候选。
22. 24起点 2 比终点 3 小,把 mid 及它左边整段灰掉,l 收到 2。窗口收空,保留的候选下标 2 就是位置。
23. 25二分结束,l 停在下标 2(起点 3 ≥ 终点 3)。注意答案要的是「原区间编号」,查侧栏面板:排序下标 2 对应原区间 1，所以 区间 2=[2, 3] 的答案是 1。
24. 26现在处理 区间 3=[5, 6]。它的右侧区间,就是「起点 ≥ 它的终点 6」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 6 的起点。
25. 27搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它比终点 6 小,接不住这个终点,它和它左边都排除掉,到右边继续找。
26. 28起点 3 比终点 6 小,把 mid 及它左边整段灰掉,l 收到 3。继续往右找第一个够大的起点。
27. 29搜索窗口 [3, 4) 的正中间是下标 3，起点 5。它比终点 6 小,接不住这个终点,它和它左边都排除掉,到右边继续找。
28. 30起点 5 比终点 6 小,把 mid 及它左边整段灰掉,l 收到 4。窗口收空且一直没有候选,说明没有起点 ≥ 6，答案是 -1。
29. 31二分结束,l 被一路推到 4，等于数组长度,说明所有起点都比终点 6 小,谁也接不住它。区间 3=[5, 6] 没有右侧区间,答案记 -1。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        ans = [-1] * n
        arr = sorted((st, i) for i, (st, _) in enumerate(intervals))
        for i, (_, ed) in enumerate(intervals):
            j = bisect_left(arr, (ed, -inf))
            if j < n:
                ans[i] = arr[j][1]
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<pair<int, int>> arr;
        for (int i = 0; i < n; ++i) {
            arr.emplace_back(intervals[i][0], i);
        }
        sort(arr.begin(), arr.end());
        vector<int> ans;
        for (auto& e : intervals) {
            int j = lower_bound(arr.begin(), arr.end(), make_pair(e[1], -1)) - arr.begin();
            ans.push_back(j == n ? -1 : arr[j].second);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] arr = new int[n][0];
        for (int i = 0; i < n; ++i) {
            arr[i] = new int[] {intervals[i][0], i};
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int j = search(arr, intervals[i][1]);
            ans[i] = j < n ? arr[j][1] : -1;
        }
        return ans;
    }

    private int search(int[][] arr, int x) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (arr[mid][0] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

复杂度

面试官可能追问