題目描述:給定一組區間 intervals(每個區間 [left, right])和一組查詢點 queries。對於每個查詢點,找出包含該點的最小區間(長度定義為 right - left + 1),並回傳其大小。若無區間包含該查詢點,回傳 -1。
解題思路:使用排序加最小堆(min-heap)的離線掃描線算法。
步驟一:對 intervals 按起始點 left 排序。對 queries 排序,但需保留原始索引(因為答案必須按原順序輸出)。
步驟二:初始化一個最小堆,按「區間大小」排序,堆中每個元素為 (size, right),表示某個區間的大小與右端點。使用指標 i 指向下一個待處理的區間。
步驟三:按排序後的查詢點順序處理每個查詢 q:
left <= q 的區間加入堆中(用 i 指標順序掃描)。這些區間的左端點不超過 q,是潛在的候選。right < q 的區間(右端點不夠大,不包含 q)。q 且大小最小的區間,記錄其 size;否則記錄 -1。關鍵:由於查詢按升序排列,每個區間只會被加入堆一次;區間的淘汰也是單調的,故總操作次數為 O((n+q) log n)。
時間複雜度:O((n + q) log n) — 排序區間為 O(n log n),排序查詢為 O(q log q);每個區間最多被加入堆一次、從堆彈出一次,各為 O(log n);每個查詢做常數次堆操作,總堆操作為 O((n + q) log n)。
空間複雜度:O(n + q) — 堆最多儲存 n 個區間;排序查詢陣列需要 O(q) 額外空間;輸出陣列 O(q)。
1. Sort intervals by start time.
2. Create sortedQ = [(queries[i], i) for all i], then sort by query value.
3. Initialize minHeap (min-heap by interval size), pointer i = 0, result array.
4. For each (queryVal, origIdx) in sortedQ:
a. While i < n and intervals[i].start <= queryVal:
- Push (intervals[i].size, intervals[i].end) into minHeap.
- Increment i.
b. While minHeap not empty and minHeap.top().end < queryVal:
- Pop from minHeap.
c. result[origIdx] = minHeap.empty() ? -1 : minHeap.top().size.
5. Return result.暴力法 O(n * q):對每個查詢,線性掃描所有區間,找出包含該查詢點且大小最小的區間。對小輸入可行,但對本題的資料規模(n, q 各可達 10^5)會超時。
線段樹 / 區間樹 O((n + q) log n):建立區間樹,支援「找包含某點的最小區間」的查詢。實作複雜度較高,但在需要支援在線(online)查詢(即查詢不可排序)的場景下更有優勢;本題由於允許離線處理,掃描線 + 堆的方式更簡潔。