题目描述
思路解析动画文字版
记住三步:① 起点带原下标一起排序;② 对每个区间的终点 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题