题目描述
思路解析
一句话答案：LeetCode 436 寻找右区间:给每个区间找起点≥自己终点、且最靠左的那个区间。把起点连原下标排序,对每个终点二分找第一个 ≥ 它的起点、查回下标,没有记 -1,时间 O(n log n)。
每个区间要找的『右侧区间』,到底是哪一个
给一组区间 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²) 快一个量级。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三步:① 起点带原下标一起排序;② 对每个区间的终点 end,二分找第一个 ≥ end 的起点(所在区间);③ 用原下标映射回答案。下面每帧都在套它。
先把四个区间的起点单独拎出来:1、3、2、5，它们的原区间编号依次是 0、1、2、3。直接二分需要有序,所以下一步排序;但排序会打乱顺序,必须把「原区间编号」绑在每个起点身上一起搬。
排序完成,起点升序排好:1、2、3、5。看右边侧栏,这是全篇的关键账本:排序下标 0 到 3 分别对应原区间 0、2、1、3。二分会在这个有序数组上定位,定位后再查账本换回原区间编号。
现在处理 区间 0=[1, 2]。它的右侧区间,就是「起点 ≥ 它的终点 2」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 2 的起点。
搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它 ≥ 终点 2，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。
把起点 3 记成新的、更靠左的候选(绿色移到下标 2),只把它右边灰掉。接着到它左边找有没有更小、也合格的起点。
搜索窗口 [0, 2) 的正中间是下标 1，起点 2。它 ≥ 终点 2，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。绿色那格是目前记下的候选。
把起点 2 记成新的、更靠左的候选(绿色移到下标 1),只把它右边灰掉。接着到它左边找有没有更小、也合格的起点。
搜索窗口 [0, 1) 的正中间是下标 0，起点 1。它比终点 2 小,接不住这个终点,它和它左边都排除掉,到右边继续找。绿色那格是目前记下的候选。
起点 1 比终点 2 小,把 mid 及它左边整段灰掉,l 收到 1。窗口收空,保留的候选下标 1 就是位置。
二分结束,l 停在下标 1(起点 2 ≥ 终点 2)。注意答案要的是「原区间编号」,查侧栏面板:排序下标 1 对应原区间 2，所以 区间 0=[1, 2] 的答案是 2。
现在处理 区间 1=[3, 4]。它的右侧区间,就是「起点 ≥ 它的终点 4」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 4 的起点。
搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它比终点 4 小,接不住这个终点,它和它左边都排除掉,到右边继续找。
起点 3 比终点 4 小,把 mid 及它左边整段灰掉,l 收到 3。继续往右找第一个够大的起点。
搜索窗口 [3, 4) 的正中间是下标 3，起点 5。它 ≥ 终点 4，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。
把起点 5 记成新的、更靠左的候选(绿色移到下标 3),只把它右边灰掉。此时窗口 [3, 3) 收空,保留的候选下标 3 就是要找的位置。
二分结束,l 停在下标 3(起点 5 ≥ 终点 4)。注意答案要的是「原区间编号」,查侧栏面板:排序下标 3 对应原区间 3，所以 区间 1=[3, 4] 的答案是 3。
现在处理 区间 2=[2, 3]。它的右侧区间,就是「起点 ≥ 它的终点 3」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 3 的起点。
搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它 ≥ 终点 3，本身就是一个可行候选,记成绿色;再到它左边看有没有起点更小、也合格的。
把起点 3 记成新的、更靠左的候选(绿色移到下标 2),只把它右边灰掉。接着到它左边找有没有更小、也合格的起点。
搜索窗口 [0, 2) 的正中间是下标 1，起点 2。它比终点 3 小,接不住这个终点,它和它左边都排除掉,到右边继续找。绿色那格是目前记下的候选。
起点 2 比终点 3 小,把 mid 及它左边整段灰掉,l 收到 2。窗口收空,保留的候选下标 2 就是位置。
二分结束,l 停在下标 2(起点 3 ≥ 终点 3)。注意答案要的是「原区间编号」,查侧栏面板:排序下标 2 对应原区间 1，所以 区间 2=[2, 3] 的答案是 1。
现在处理 区间 3=[5, 6]。它的右侧区间,就是「起点 ≥ 它的终点 6」里起点最小的那个。我们就在排序后的起点数组里,用左闭右开 [0, 4) 二分,找第一个 ≥ 6 的起点。
搜索窗口 [0, 4) 的正中间是下标 2，起点 3。它比终点 6 小,接不住这个终点,它和它左边都排除掉,到右边继续找。
起点 3 比终点 6 小,把 mid 及它左边整段灰掉,l 收到 3。继续往右找第一个够大的起点。
搜索窗口 [3, 4) 的正中间是下标 3，起点 5。它比终点 6 小,接不住这个终点,它和它左边都排除掉,到右边继续找。
起点 5 比终点 6 小,把 mid 及它左边整段灰掉,l 收到 4。窗口收空且一直没有候选,说明没有起点 ≥ 6，答案是 -1。
二分结束,l 被一路推到 4，等于数组长度,说明所有起点都比终点 6 小,谁也接不住它。区间 3=[5, 6] 没有右侧区间,答案记 -1。
边界要想清:单区间常是 -1;但 j 可以等于 i，起点 ≥ 自己终点时答案就是自己;末尾区间通常 -1。
认出「lower_bound 找第一个 ≥ 的位置」+「排序带原下标」两个点,这题就透了。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n log n)，排序 O(n log n) + n 次二分合计 O(n log n)
- 空间：O(n)，存放排序后的 (起点, 原下标) 数组
易错点
面试追问把动画讲成自己的话
追问为什么能用二分?这题哪里有序?
追问排序破坏了原顺序,怎么还原答案下标?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按权重随机选择
LeetCode 528 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题