【每日一题Day269】LC1851包含每个查询的最小区间 | 排序+离线查询+小顶堆

**每日一题 Day269**

**包含每个查询的最小区间**

今天，我们来解决一个有趣的问题：给定一个整数数组 `nums` 和一个二维数组 `queries`，其中 `queries[i] = [starti, endi]` 表示从 `starti` 到 `endi` 的区间。我们需要找到包含每个查询的最小区间。

**示例1**

输入：`nums = [4,5,6,7,8]`, `queries = [[2,4],[0,4],[1,3]]`

输出：`[[4,7],[0,7],[1,6]]`

**示例2**

输入：`nums = [4,5,6,7,8]`, `queries = [[1,3],[0,2]]`

输出：`[[5,6],[4,6]]`

**解决方案**

我们可以使用一个小顶堆来解决这个问题。具体来说，我们会维护一个小顶堆，包含所有可能的最小区间。

首先，我们需要将 `nums` 中的每个数字都放入小顶堆中。这样做的目的是确保小顶堆中的每个元素都是当前最小的区间。

接下来，我们遍历 `queries` 中的每个查询。对于每个查询，我们会从小顶堆中取出一个元素，并将其与当前的最小区间进行比较。如果新的元素是更小的，则我们更新最小区间并将新元素放回小顶堆。

最后，我们返回所有最小区间的集合。

**代码实现**

import heapqclass Solution:
 def minInterval(self, nums: List[int], queries: List[List[int]]) -> List[List[int]]:
 # 将 nums 中的每个数字都放入小顶堆中 heap = []
 for num in nums:
 heapq.heappush(heap, (num, num))

 # 初始化最小区间和答案列表 min_interval = float('inf')
 ans = []

 # 遍历 queries 中的每个查询 for start, end in queries:
 while heap and heap[0][1] <= end:
 _, val = heapq.heappop(heap)
 min_interval = min(min_interval, val)

 # 如果最小区间是当前最小的，则更新答案列表 if min_interval < float('inf'):
 ans.append([min_interval, max(nums)])

 return ans