What is the core pattern in solving 'Minimum Interval to Include Each Query'?

The core pattern involves binary search to find the smallest interval containing each query, with optimizations like sorting intervals and using a heap.

How does binary search help in solving this problem?

Binary search helps by efficiently narrowing down the search space for each query, minimizing the number of comparisons needed to find the valid interval.

What is the time complexity of this problem?

The time complexity is O(n log n + m log n), where n is the number of intervals and m is the number of queries.

What are common pitfalls when solving this problem?

Common pitfalls include not sorting intervals, not using a heap to manage active intervals, and missing edge cases where no interval contains a query.

Can GhostInterview help with advanced variations of this problem?

Yes, GhostInterview can provide hints and optimizations for handling larger ranges, pre-sorted intervals, and other advanced variations of this problem.

#1851

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

包含每个查询的最小区间

给你一个二维整数数组 intervals ，其中 intervals[i] = [left i , right i ] 表示第 i 个区间开始于 left i 、结束于 right i （包含两侧取值，闭区间）。区间的长度定义为区间中包含的整数数目，更正式地表达是 right i - lef…

数组二分查找扫描线排序堆（优先队列）

题目描述

给你一个二维整数数组 intervals ，其中 intervals[i] = [left_i, right_i] 表示第 i 个区间开始于 left_i 、结束于 right_i（包含两侧取值，闭区间）。区间的长度定义为区间中包含的整数数目，更正式地表达是 right_i - left_i + 1 。

再给你一个整数数组 queries 。第 j 个查询的答案是满足 left_i <= queries[j] <= right_i 的 长度最小区间 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 <= 10⁵
1 <= queries.length <= 10⁵
intervals[i].length == 2
1 <= left_i <= right_i <= 10⁷
1 <= queries[j] <= 10⁷

lightbulb

解题思路

方法一：排序 + 离线查询 + 优先队列（小根堆）

我们注意到，题目中查询的顺序并不会影响答案，并且涉及到的区间也不会发生变化，因此，我们考虑将所有的查询按照从小到大的顺序进行排序，同时将所有的区间按照左端点从小到大的顺序进行排序。

我们使用一个优先队列（小根堆） $pq$ 来维护当前所有的区间，队列的每个元素是一个二元组 $(v, r)$ ，表示一个区间长度为 $v$ ，右端点为 $r$ 的区间。初始时，优先队列为空。另外，我们定义一个指针 $i$ ，指向当前遍历到的区间，初始时 $i=0$ 。

我们按照从小到大的顺序依次遍历每个查询 $(x, j)$ ，并进行如下操作：

如果指针 $i$ 尚未遍历完所有的区间，并且当前遍历到的区间 $[a, b]$ 的左端点小于等于 $x$ ，那么我们将该区间加入优先队列中，并将指针 $i$ 后移一位，循环此过程；
如果优先队列不为空，并且堆顶元素的右端点小于 $x$ ，那么我们将堆顶元素弹出，循环此过程；
此时，如果优先队列不为空，那么堆顶元素就是包含 $x$ 的最小区间。我们将其长度 $v$ 加入答案数组 $ans$ 中。

在上述过程结束后，我们返回答案数组 $ans$ 即可。

时间复杂度 $O(n \times \log n + m \times \log m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是数组 $intervals$ 和 $queries$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands how to use sorting to optimize interval processing.
question_mark
Candidate demonstrates knowledge of binary search in finding the correct interval.
question_mark
Candidate correctly applies a heap to minimize computational time during interval queries.

warning

常见陷阱

外企场景

error
Not sorting the intervals before applying binary search leads to inefficient solutions.
error
Failing to use the heap structure efficiently could result in higher-than-expected complexity.
error
Not handling cases where no interval contains the query could lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the intervals are already sorted?
arrow_right_alt
How would you handle queries that are out of bounds of all the intervals?
arrow_right_alt
What if you need to handle a larger range of values, say up to 10^9?

help

常见问题

外企场景

继续练习

#1648 销售价值减少的颜色球 #2054 两个最好的不重叠活动 #2333 最小差值平方和