1851. Minimum Interval to Include Each Query
解題說明
Minimum Interval to Include Each Query
題目描述：給定一組區間 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)。
C++ 解法
複雜度分析
時間複雜度：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）查詢（即查詢不可排序）的場景下更有優勢；本題由於允許離線處理，掃描線 + 堆的方式更簡潔。
延伸思考
- 如果將「最小區間」改為「包含查詢點的所有區間中，右端點最小的那個」，算法應如何修改？
- 此題採用離線算法（先對查詢排序後再處理）。若查詢必須在線逐一到達（無法預先排序），最佳的解法是什麼？複雜度如何？
- 考慮一個變形：若同一個區間可以被選中回答多個查詢，且每次使用會讓區間「縮小」1（即右端點減 1），如何找到每個查詢的最小可用區間？