資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢包含每個查詢的最小區間
假設我們有一個區間列表，其中intervals[i]包含一對(left_i, right_i)，表示第i個區間從left_i開始，到right_i結束（均包含）。我們還有一個名為queries的陣列。第j個查詢的答案是包含queries[j]的最小區間i的大小，即right_i - left_i + 1。如果我們找不到這樣的區間，則返回-1。我們必須找到一個包含查詢答案的陣列。
因此，如果輸入類似於intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6]，則輸出將為[3, 3, 1, 4]，因為查詢按以下方式處理：
對於查詢= 3：區間[3,5]是最小的包含3的區間。所以，5 - 3 + 1 = 3。
對於查詢= 4：區間[3,5]是最小的包含4的區間。所以，5 - 3 + 1 = 3。
對於查詢= 5：區間[5,5]是最小的包含5的區間。所以，5 - 5 + 1 = 1。
對於查詢= 6：區間[4,7]是最小的包含6的區間。所以，7 - 4 + 1 = 4。
為了解決這個問題，我們將遵循以下步驟：
intervals := 將區間列表intervals按降序排序
h := 一個新的列表
res := 一個新的對映
對於排序後的查詢列表中的每個q，執行以下操作：
當intervals不為空且最後一個區間的結束時間小於等於q時，執行以下操作：
(i, j) := intervals中的最後一個區間，並將其移除
如果j大於等於q，則
將(j-i+1, j)插入堆h中
當h不為空且h中頂部區間的結束時間小於q時，執行以下操作：
從h中刪除頂部元素
如果h不為空，則res[q] := h中頂部區間的起始時間，否則res[q] := -1
返回queries中所有q的res[q]列表
示例
讓我們檢視以下實現以獲得更好的理解
import heapq
def solve(intervals, queries):
intervals = sorted(intervals)[::-1]
h = []
res = {}
for q in sorted(queries):
while intervals and intervals[-1][0] <= q:
i, j = intervals.pop()
if j >= q:
heapq.heappush(h, [j - i + 1, j])
while h and h[0][1] < q:
heapq.heappop(h)
res[q] = h[0][0] if h else -1
return [res[q] for q in queries]
intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries))輸入
[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]
輸出
[3, 3, 1, 4]
301 次瀏覽
