包含每个查询的最小区间 图解题解
这道题到底在问什么
- 输入
- intervals=[[1,3],[2,8],[3,5],[6,9],[7,7]]，queries=[2,4,7,9]
- 输出
- [3,3,1,4]
最优解：一步一步想明白
- 3三个动作循环套：① 左端点够得着的区间进堆 ② 右端点盖不住的区间出堆 ③ 堆顶就是答案。查询从小到大，区间只进不退，所以每个区间最多进堆出堆一次。
- 4准备阶段：区间已按左端点从小到大排好，每格里的数字是这个区间的长度。指针 p 指向下一个待入堆的区间，堆现在是空的。
- 5轮到查询 q=2。先看哪些区间的左端点已经够得着它、要进堆，再把盖不住它的弹出去，最后读堆顶。
- 6查询 q=2：区间 [1,3] 的左端点 1 不超过 2，左边已经够得着，把它(长度 3)推进堆。
- 7查询 q=2：区间 [2,8] 的左端点 2 不超过 2，左边已经够得着，把它(长度 7)推进堆。
- 8查询 q=2：指针 p 停在区间 [3,5]，它的左端点 3 比 2 还大，左边都够不着 2，这一轮先不推它，等更大的查询再说。
- 9查询 q=2：堆里剩下的区间都真包含 2，其中最短的是 [1,3](长度 3)——标红的就是它，于是 q=2 的答案记为 3。
- 10轮到查询 q=4。先看哪些区间的左端点已经够得着它、要进堆，再把盖不住它的弹出去，最后读堆顶。
- 11查询 q=4：区间 [3,5] 的左端点 3 不超过 4，左边已经够得着，把它(长度 3)推进堆。
- 12查询 q=4：指针 p 停在区间 [6,9]，它的左端点 6 比 4 还大，左边都够不着 4，这一轮先不推它，等更大的查询再说。
- 13查询 q=4：[1,3] 的右端点已经小于 4，再也盖不住这个点了，从堆里弹掉。
- 14查询 q=4：堆里剩下的区间都真包含 4，其中最短的是 [3,5](长度 3)——标红的就是它，于是 q=4 的答案记为 3。
- 15轮到查询 q=7。先看哪些区间的左端点已经够得着它、要进堆，再把盖不住它的弹出去，最后读堆顶。
- 16查询 q=7：区间 [6,9] 的左端点 6 不超过 7，左边已经够得着，把它(长度 4)推进堆。
- 17查询 q=7：区间 [7,7] 的左端点 7 不超过 7，左边已经够得着，把它(长度 1)推进堆。
- 18查询 q=7：指针 p 已经把所有区间都看过了，没有新的区间能进堆，直接进入下一步。
- 19查询 q=7：[3,5] 的右端点已经小于 7，再也盖不住这个点了，从堆里弹掉。
- 20查询 q=7：堆里剩下的区间都真包含 7，其中最短的是 [7,7](长度 1)——标红的就是它，于是 q=7 的答案记为 1。
- 21轮到查询 q=9。先看哪些区间的左端点已经够得着它、要进堆，再把盖不住它的弹出去，最后读堆顶。
- 22查询 q=9：指针 p 已经把所有区间都看过了，没有新的区间能进堆，直接进入下一步。
- 23查询 q=9：[2,8]、[7,7] 的右端点已经小于 9，再也盖不住这个点了，从堆里弹掉。
- 24查询 q=9：堆里剩下的区间都真包含 9，其中最短的是 [6,9](长度 4)——标红的就是它，于是 q=9 的答案记为 4。
- 25四个查询从小到大依次扫完，每个查询都在「进堆、出堆、读堆顶」三步里拿到了自己的最短区间长度，最终答案是 [3,3,1,4]。
⚠️ 容易写错的地方
✗ 错：查询不排序，直接按原顺序处理
✓ 对：先把查询从小到大排序，处理完再按原下标放回答案
指针 p 只能往前走、区间只进不退，靠的就是查询单调递增；乱序会漏推区间
✗ 错：堆里只存长度，弹出时不知道右端点
✓ 对：堆里存 (长度, 右端点)，按长度排序、按右端点判过期
判断一个区间是否还盖得住 q 要看它的右端点，丢了右端点就没法弹过期区间
✗ 错：先弹过期、后推入新区间
✓ 对：先推入左端够得着的，再弹掉右端盖不住的
顺序反了会把刚该进堆、其实有效的区间也一起误判，逻辑虽常能凑对但容易出错
完整代码（Python / C++ / Java）
Python
import heapq
def minInterval(intervals, queries):
intervals.sort() # 按左端点排序
heap, ans, p = [], {}, 0
for q in sorted(queries): # 查询从小到大
while p < len(intervals) and intervals[p][0] <= q:
l, r = intervals[p]
heapq.heappush(heap, (r - l + 1, r)) # (长度, 右端)
p += 1
while heap and heap[0][1] < q: # 弹掉盖不住的
heapq.heappop(heap)
ans[q] = heap[0][0] if heap else -1 # 堆顶最短
return [ans[q] for q in queries]C++
vector<int> minInterval(vector<vector<int>>& iv, vector<int>& qs){
sort(iv.begin(), iv.end());
vector<pair<int,int>> q; // (查询值, 原下标)
for (int i = 0; i < qs.size(); i++) q.push_back({qs[i], i});
sort(q.begin(), q.end());
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
vector<int> ans(qs.size(), -1); int p = 0;
for (auto& [val, idx] : q) {
while (p < iv.size() && iv[p][0] <= val)
pq.push({iv[p][1]-iv[p][0]+1, iv[p][1]}), p++;
while (!pq.empty() && pq.top().second < val) pq.pop();
if (!pq.empty()) ans[idx] = pq.top().first;
}
return ans;
}Java
public int[] minInterval(int[][] iv, int[] qs) {
Arrays.sort(iv, (a, b) -> a[0] - b[0]);
Integer[] q = new Integer[qs.length];
for (int i = 0; i < qs.length; i++) q[i] = i;
Arrays.sort(q, (a, b) -> qs[a] - qs[b]);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int[] ans = new int[qs.length]; Arrays.fill(ans, -1); int p = 0;
for (int idx : q) {
while (p < iv.length && iv[p][0] <= qs[idx])
pq.offer(new int[]{iv[p][1]-iv[p][0]+1, iv[p][1]}), p++;
while (!pq.isEmpty() && pq.peek()[1] < qs[idx]) pq.poll();
if (!pq.isEmpty()) ans[idx] = pq.peek()[0];
}
return ans;
}复杂度
时间
O((n+q)·log n)
区间和查询各排序 O(n log n + q log q)；每个区间最多进堆出堆一次，堆操作各 O(log n)
空间
O(n+q)
堆最多装下全部区间 O(n)，再加保存查询顺序与答案 O(q)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 包含每个查询的最小区间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
堆里到底存什么？为什么按长度排序？+
存 (区间长度, 右端点)。题目要的是「最短的包含区间」，所以用长度做堆的排序键，堆顶就是当前最短；右端点用来判断这个区间是否已经盖不住当前查询、该不该弹出。
一个区间会被反复进堆出堆吗？+
不会。查询从小到大处理，指针 p 只前进，每个区间最多入堆一次；它要么在某个查询时因右端点过期被弹出一次，要么一直留到最后。所以总的堆操作是 O(n log n)。
如果某查询没有任何区间包含它，怎么处理？+
把所有过期区间弹完后堆为空，答案记 -1。注意要按查询的原始下标把答案放回，因为我们是按排序后的顺序算的。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 包含每个查询的最小区间 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。