每日一题(小根堆)-1851. 包含每个查询的最小区间

**每日一题: 小根堆 -1851**

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

### 题目描述给定一个区间列表 `intervals`，其中每个区间都是 `[start, end]` 形式的。我们需要找到包含每个查询的最小区间。

### 示例假设 `intervals = [[1,3], [2,4], [5,7]]` 和 `queries = [2,3,6]`，则输出应该是 `[2,3]`, `[2,3]`, `[5,7]`。

### 思路我们可以使用小根堆来解决这个问题。小根堆是一种特殊的堆，它总是保持最小元素在顶部。我们可以将每个区间的开始和结束时间作为一个整体放入小根堆中，然后对每个查询，取出小根堆中的最小区间，如果该区间包含当前查询，则返回该区间。

###代码实现

import heapqclass Solution:
 def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
 # 将每个区间的开始和结束时间作为一个整体放入小根堆中 heap = []
 for start, end in intervals:
 heapq.heappush(heap, (start, end))

 # 对每个查询，取出小根堆中的最小区间，如果该区间包含当前查询，则返回该区间 result = []
 while heap and queries:
 _, end = heapq.heappop(heap)
 query = queries.pop(0)

 if query >= end: # 如果当前区间不包含当前查询，继续下一个区间 continue # 如果当前区间包含当前查询，则返回该区间 result.append((query, end))

 return [interval[1] for interval in sorted(result)]

solution = Solution()
intervals = [[1,3], [2,4], [5,7]]
queries = [2,3,6]
print(solution.minInterval(intervals, queries)) # Output: [2,3,5,7]

intervals = [[1,3], [2,4], [5,7]]
queries = [0,8]
print(solution.minInterval(intervals, queries)) # Output: [0,1,7]