Description
給定一個二維陣列
intervals（intervals[i] = [left_i, right_i]）和一個查詢陣列queries。對每個查詢q，找出包含q的最小區間長度（right - left + 1）。如果沒有區間包含q，答案為 -1。
Example:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Output: [3,3,1,4]
Intuition#
離線處理：將查詢排序後，配合排序的區間和 min-heap，逐步處理每個查詢。
- 暴力對每個查詢檢查所有區間是
O(n * q)，太慢 - 離線排序：將查詢和區間都按位置排序
- 用 min-heap 按區間長度排序，維護所有可能包含當前查詢的區間
Approaches#
1: Brute Force#
- 概念: 對每個查詢遍歷所有區間，找包含它的最小區間
- 時間複雜度:
O(n * q)— n 為區間數，q 為查詢數 - 空間複雜度:
O(q)— 輸出空間
class Solution {
fun minInterval(intervals: Array<IntArray>, queries: IntArray): IntArray {
val result = IntArray(queries.size)
for (i in queries.indices) {
var minSize = Int.MAX_VALUE
for (interval in intervals) {
if (interval[0] <= queries[i] && queries[i] <= interval[1]) {
minSize = minOf(minSize, interval[1] - interval[0] + 1)
}
}
result[i] = if (minSize == Int.MAX_VALUE) -1 else minSize
}
return result
}
}⭐2: Offline Sort + Min-Heap#
- 概念: 將區間按起點排序，查詢按值排序（保留原始索引）。對每個查詢，將所有起點 <= 查詢值的區間加入 min-heap（按長度排序），再移除終點 < 查詢值的無效區間，堆頂即為答案。
- 時間複雜度:
O((n + q) log n) - 空間複雜度:
O(n + q)
class Solution {
fun minInterval(intervals: Array<IntArray>, queries: IntArray): IntArray {
// 區間按起點排序
intervals.sortBy { it[0] }
// 查詢排序但保留原始索引
val sortedQueries = queries.indices.sortedBy { queries[it] }
// min-heap: (區間長度, 區間終點)
val heap = java.util.PriorityQueue<IntArray>(compareBy { it[0] })
val result = IntArray(queries.size) { -1 }
var idx = 0
for (qi in sortedQueries) {
val q = queries[qi]
// 將所有起點 <= q 的區間加入 heap
while (idx < intervals.size && intervals[idx][0] <= q) {
val size = intervals[idx][1] - intervals[idx][0] + 1
heap.add(intArrayOf(size, intervals[idx][1]))
idx++
}
// 移除終點 < q 的區間（不再包含 q）
while (heap.isNotEmpty() && heap.peek()[1] < q) {
heap.poll()
}
if (heap.isNotEmpty()) {
result[qi] = heap.peek()[0]
}
}
return result
}
}🔑 Takeaways#
- Pattern: 離線查詢 + Sweep — 當查詢可以排序處理時，離線排序配合堆可以大幅降低複雜度
- 關鍵技巧: 離線處理的核心是「排序後單調推進」：區間只會被加入 heap 一次，也只會被移除一次，攤平後每個操作都是
O(log n)