1851. 包含每个查询的最小区间
April 12, 2026 · View on GitHub
题目描述
给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。
再给你一个整数数组 queries 。第 j 个查询的答案是满足 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 。
提示：
1 <= intervals.length <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107
解法
方法一：排序 + 离线查询 + 优先队列（小根堆）
我们注意到，题目中查询的顺序并不会影响答案，并且涉及到的区间也不会发生变化，因此，我们考虑将所有的查询按照从小到大的顺序进行排序，同时将所有的区间按照左端点从小到大的顺序进行排序。
我们使用一个优先队列（小根堆） 来维护当前所有的区间，队列的每个元素是一个二元组 ，表示一个区间长度为 ，右端点为 的区间。初始时，优先队列为空。另外，我们定义一个指针 ，指向当前遍历到的区间，初始时 。
我们按照从小到大的顺序依次遍历每个查询 ，并进行如下操作：
- 如果指针 尚未遍历完所有的区间，并且当前遍历到的区间 的左端点小于等于 ，那么我们将该区间加入优先队列中，并将指针 后移一位，循环此过程；
- 如果优先队列不为空，并且堆顶元素的右端点小于 ，那么我们将堆顶元素弹出，循环此过程；
- 此时，如果优先队列不为空，那么堆顶元素就是包含 的最小区间。我们将其长度 加入答案数组 中。
在上述过程结束后，我们返回答案数组 即可。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度。
Python3
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
Java
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
int n = intervals.length, m = queries.length;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int[][] qs = new int[m][0];
for (int i = 0; i < m; ++i) {
qs[i] = new int[] {queries[i], i};
}
Arrays.sort(qs, (a, b) -> a[0] - b[0]);
int[] ans = new int[m];
Arrays.fill(ans, -1);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int i = 0;
for (int[] q : qs) {
while (i < n && intervals[i][0] <= q[0]) {
int a = intervals[i][0], b = intervals[i][1];
pq.offer(new int[] {b - a + 1, b});
++i;
}
while (!pq.isEmpty() && pq.peek()[1] < q[0]) {
pq.poll();
}
if (!pq.isEmpty()) {
ans[q[1]] = pq.peek()[0];
}
}
return ans;
}
}
C++
class Solution {
public:
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
int n = intervals.size(), m = queries.size();
sort(intervals.begin(), intervals.end());
using pii = pair<int, int>;
vector<pii> qs;
for (int i = 0; i < m; ++i) {
qs.emplace_back(queries[i], i);
}
sort(qs.begin(), qs.end());
vector<int> ans(m, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq;
int i = 0;
for (auto& [x, j] : qs) {
while (i < n && intervals[i][0] <= x) {
int a = intervals[i][0], b = intervals[i][1];
pq.emplace(b - a + 1, b);
++i;
}
while (!pq.empty() && pq.top().second < x) {
pq.pop();
}
if (!pq.empty()) {
ans[j] = pq.top().first;
}
}
return ans;
}
};
Go
func minInterval(intervals [][]int, queries []int) []int {
n, m := len(intervals), len(queries)
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
qs := make([][2]int, m)
ans := make([]int, m)
for i := range qs {
qs[i] = [2]int{queries[i], i}
ans[i] = -1
}
sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
pq := hp{}
i := 0
for _, q := range qs {
x, j := q[0], q[1]
for i < n && intervals[i][0] <= x {
a, b := intervals[i][0], intervals[i][1]
heap.Push(&pq, pair{b - a + 1, b})
i++
}
for len(pq) > 0 && pq[0].r < x {
heap.Pop(&pq)
}
if len(pq) > 0 {
ans[j] = pq[0].v
}
}
return ans
}
type pair struct{ v, r int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
TypeScript
function minInterval(intervals: number[][], queries: number[]): number[] {
const n = intervals.length;
const m = queries.length;
intervals.sort((a, b) => a[0] - b[0]);
const qs = queries.map((x, i) => [x, i] as [number, number]).sort((a, b) => a[0] - b[0]);
const ans = Array<number>(m).fill(-1);
const pq = new PriorityQueue<[number, number]>((a, b) =>
a[0] === b[0] ? a[1] - b[1] : a[0] - b[0],
);
let i = 0;
for (const [x, idx] of qs) {
while (i < n && intervals[i][0] <= x) {
const [l, r] = intervals[i];
pq.enqueue([r - l + 1, r]);
i++;
}
while (pq.size() > 0 && pq.front()![1] < x) {
pq.dequeue();
}
if (pq.size() > 0) {
ans[idx] = pq.front()![0];
}
}
return ans;
}
Rust
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
pub fn min_interval(intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
let mut intervals = intervals;
intervals.sort_by_key(|v| v[0]);
let mut sorted_queries: Vec<(i32, usize)> = queries
.into_iter()
.enumerate()
.map(|(i, x)| (x, i))
.collect();
sorted_queries.sort_by_key(|&(x, _)| x);
let mut ans = vec![-1; sorted_queries.len()];
let mut heap: BinaryHeap<Reverse<(i32, i32)>> = BinaryHeap::new();
let mut i = 0usize;
for (x, idx) in sorted_queries {
while i < intervals.len() && intervals[i][0] <= x {
let l = intervals[i][0];
let r = intervals[i][1];
heap.push(Reverse((r - l + 1, r)));
i += 1;
}
while let Some(&Reverse((_, r))) = heap.peek() {
if r < x {
heap.pop();
} else {
break;
}
}
if let Some(&Reverse((len, _))) = heap.peek() {
ans[idx] = len;
}
}
ans
}
}