1 包含每个查询的最小区间
1.1 题目描述
给你一个二维整数数组 intervals ，其中
i
n
t
e
r
v
a
l
s
[
i
]
=
[
l
e
f
t
i
,
r
i
g
h
t
i
]
intervals[i] = [left_i, right_i]
intervals[i]=[lefti,righti] 表示第
i
i
i 个区间开始于
l
e
f
t
i
left_i
lefti 、结束于
r
i
g
h
t
i
right_i
righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是
r
i
g
h
t
i
−
l
e
f
t
i
+
1
right_i - left_i + 1
righti−lefti+1。
再给你一个整数数组 queries 。第 j 个查询的答案是满足
l
e
f
t
i
<
=
q
u
e
r
i
e
s
[
j
]
<
=
r
i
g
h
t
i
left_i <= queries[j] <= right_i
lefti<=queries[j]<=righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。
以数组形式返回对应查询的所有答案。
示例 1：
输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：
- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。
示例 2
输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：
- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
- Query = 19：不存在包含 19 的区间，答案为 -1 。
- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。
解法一：区间端点排序+离线查询+优先队列（小根堆）
首先我们对问题进行分析，对于第
j
j
j 个查询，可以遍历
intervals
\textit{intervals}
intervals，找到满足
left
i
≤
queries
j
≤
right
i
\textit{left}_i \le \textit{queries}_j \le \textit{right}_i
lefti≤queriesj≤righti 的长度最小区间
i
i
i 的长度。以上思路对于每个查询，都需要重新遍历
intervals
\textit{intervals}
intervals。
如果查询是递增的，那么我们可以对
intervals
\textit{intervals}
intervals 按左端点
left
\textit{left}
left 从小到大进行排序，使用一个指针
i
i
i 记录下一个要访问的区间
intervals
[
i
]
\textit{intervals}[i]
intervals[i]，初始时
i
=
0
i = 0
i=0，使用优先队列
pq
\textit{pq}
pq 保存区间（优先队列的比较
key
\textit{key}
key 为区间的长度，队首元素为长度最小的区间）。对于第
j
j
j 个查询，我们执行以下步骤：
- 如果
i
i
i 等于
intervals
\textit{intervals}
intervals 的长度或
left
i
>
queries
[
j
]
\textit{left}_i \gt \textit{queries}[j]
lefti>queries[j]，终止步骤；
- 将
intervals
[
i
]
\textit{intervals}[i]
intervals[i] 添加到优先队列
pq
\textit{pq}
pq，将
i
i
i 的值加 1，继续执行步骤 1。
此时所有符合
left
≤
queries
j
≤
right
\textit{left} \le \textit{queries}_j \le \textit{right}
left≤queriesj≤right 的区间都在
pq
\textit{pq}
pq，我们不断地获取优先队列
pq
\textit{pq}
pq 的队首区间：
- 如果队首区间的右端点
right
<
queries
[
j
]
\textit{right} \lt \textit{queries}[j]
right<queries[j]，那么说明该区间不满足条件，从
pq
\textit{pq}
pq 中出队；
如果队首区间的右端点
right
≥
queries
[
j
]
\textit{right} \ge \textit{queries}[j]
right≥queries[j]，那么该区间为第
j
j
j 个查询的最小区间，终止过程。
对于第
j
+
1
j+1
j+1 个查询，因为查询是递增的，所以有
queries
[
j
+
1
]
≥
queries
[
j
]
\textit{queries}[j + 1] \ge \textit{queries}[j]
queries[j+1]≥queries[j]，那么此时
pq
\textit{pq}
pq 中的区间都满足
left
≤
queries
[
j
+
1
]
\textit{left} \le \textit{queries}[j + 1]
left≤queries[j+1]。在第
j
j
j 个查询中丢弃的区间有
right
<
queries
[
j
]
≤
queries
[
j
+
1
]
\textit{right} \lt \textit{queries}[j] \le \textit{queries}[j + 1]
right<queries[j]≤queries[j+1]，因此丢弃的区间不满足第
j
+
1
j + 1
j+1 个查询。同样在第
j
+
1
j + 1
j+1 个查询执行与第
j
j
j 个查询类似的步骤，将可能满足条件的区间加入优先队列
pq
\textit{pq}
pq 中，那么此时所有满足条件的区间都在优先队列
pq
\textit{pq}
pq 中，执行类似第
j
j
j 个查询的出队操作。
由以上分析，如果查询满足递增的条件，那么可以利用优先队列进行优化。题目一次性提供所有的查询，基于离线原理，我们对所有查询从小到大进行排序，然后执行以上算法。
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
n, m = len(intervals), len(queries)
intervals.sort()
queries = sorted((x, i) for i, x in enumerate(queries))
ans = [-1] * m
pq = []
i = 0
for x, j in queries:
while i < n and intervals[i][0] <= x:
a, b = intervals[i]
heappush(pq, (b - a + 1, b))
i += 1
while pq and pq[0][1] < x:
heappop(pq)
if pq:
ans[j] = pq[0][0]
return ans
复杂度分析
- 时间复杂度
O
(
n
×
log
n
+
m
×
log
m
)
O(n \times \log n + m \times \log m)
O(n×logn+m×logm)
- 空间复杂度
O
(
n
+
m
)
O(n + m)
O(n+m)。其中 n 和 m 分别是数组 intervals 和 queries 的长度。
解法二：区间长度排序+离线询问+并查集
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
m, n = len(intervals), len(queries)
intervals.sort(key=lambda x: x[1] - x[0])
queries = sorted([(q, i) for i, q in enumerate(queries)])
fa = list(range(n + 1))
def find(x):
if x != fa[x]:
fa[x] = find(fa[x])
return fa[x]
ans = [-1] * n
for l, r in intervals:
length = r - l + 1
pos = bisect_left(queries, (l, -1))
idx = find(pos)
while idx < n and queries[idx][0] <= r:
ans[queries[idx][1]] = length
fa[idx] = idx + 1
idx = find(idx + 1)
return ans
