寻找右区间 图解题解

每个区间要找的『右侧区间』,到底是哪一个

给一组区间 intervals,每个是 [start, end],所有 start 互不相同。对每个区间 i,要找一个 j:起点 start_j ≥ 当前终点 end_i,且在合格起点里最小,返回 j 的下标;没有记 -1(题目允许 j 等于 i)。题面 [[3,4],[2,3],[1,2]] 答案 [-1,0,1],返回区间下标而非起点值。

每个区间都翻遍其它所有区间,一趟 O(n²) 打底

最直接是双层循环:每个区间都把其它区间扫一遍,挑起点 ≥ 自己终点、且最小的那个。n 个区间各扫 n 遍,共 O(n²) 次比较,区间上万就是上亿次,扛不住。根子在于每次都在无序起点里从头翻找,前一个区间的比较后一个没法沿用。

右侧区间只认起点,排完序就能砍半找

一个区间的右侧区间是谁,只跟『起点』有关,跟终点、区间宽度都无关。既然只认起点,就把所有起点拎出来排成升序。排好后,『第一个 ≥ end 的起点』就落在一段有序数列里——看正中间那个,比 end 小说明它和左边全接不住、整片往右扔,够大就记下再往左找更小的。一比砍掉一半,这就是二分查找;找『第一个不小于目标的位置』就叫 lower_bound。

二分怎么收缩,原下标又怎么跟着起点走

排序埋了个坑:答案要原区间下标,排序却打乱了顺序。所以排的是 (起点, 原下标) 二元组,原下标粘着起点一起搬,定位后再取回。二分用左闭右开窗口 [l, r),l=0、r=n。取中点 mid:arr[mid] 起点 ≥ end 时是候选,r 收到 mid(它可能就是答案);起点 < end 就连左边一起作废,l 跳到 mid+1。收成 l==r 时 l 即答案位置;若 l 停在 n,起点全比 end 小、没人接得住,答案 -1。

拿 [[3,4],[2,3],[1,2]] 的三个终点各走一遍

先排序:起点带原下标 (3,0)、(2,1)、(1,2) 升序排成 arr=[(1,2),(2,1),(3,0)],排序下标 0、1、2 对应原下标 2、1、0。

每个终点都在 [0,3) 上二分。区间 0=[3,4],终点 4:起点 1、2、3 全 <4,l 推到 3=n,答案 -1。区间 1=[2,3],终点 3:mid=1 起点 2<3,l 跳到 2;mid=2 起点 3≥3,r 收到 2;l=r=2,arr[2] 原下标 0,答案 0。区间 2=[1,2],终点 2:mid=1 起点 2≥2,r 收到 1;mid=0 起点 1<2,l 跳到 1;l=r=1,arr[1] 原下标 1,答案 1。拼成 [-1,0,1]。

起点排完序,原下标别在半路弄丢了

三处最易出岔子。排序只排了起点、丢了原下标,就映射不回题目要的区间编号,所以必须排 (起点, 原下标)。判定是起点 ≥ end,相等也算合格(题目允许 j 等于 i),写成严格大于会漏掉起点正好等于终点的区间。二分收完还得查越界:l 等于 n 时数组没这个位置,硬取 arr[n] 会越界,该返回 -1。复杂度:排序与 n 次二分都是 O(n log n),空间 O(n) 存带下标的排序数组,比 O(n²) 快一个量级。

Python

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

C++

#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;
    }
};

Java

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;
    }
}