-
Notifications
You must be signed in to change notification settings - Fork 0
165 — Minimum Interval to Include Each Query
LeetCode 1851 · Hard. You're given a 2D array intervals where intervals[i] = [lefti, righti] describes an inclusive range, and an array queries. For each queries[j], find the size (right - left + 1) of the smallest interval that contains queries[j]. If no interval contains it, the answer for that query is -1. Return the answers in the same order as queries.
Picture a shelf of overlapping library reference books, each one covering a range of years, and a stack of individual year lookups you need answered. For each year someone asks about, you want the thinnest book on the shelf that still covers it — the most specific reference available, not just any book that happens to include that year. Checking every book against every lookup works, but it's wasteful. Instead, sort the lookups themselves in increasing order, and walk through them left to right: as you pass each year, bring onto your desk every book whose coverage has started by now, and toss aside any book whose coverage has already ended before this year — it can never be useful again for this or any later lookup. Among the books still on your desk, keep track of the thinnest one at all times, and that's your answer.
"Smallest interval that contains each query", with queries needing to be answered independently and out of any particular order, is the offline-sweep-plus-heap signature: sort both intervals and queries, sweep queries in increasing order while intervals become "active" as their starts are passed, and maintain a min-heap keyed by interval size so the smallest currently-valid interval is always sitting at the root — with stale (already-ended) intervals discarded lazily as queries move past them.
For each query, scan every interval directly, and keep the smallest size among the ones that actually contain it.
func minIntervalBruteForce(_ intervals: [[Int]], _ queries: [Int]) -> [Int] {
var result: [Int] = []
for q in queries {
var best = -1
for interval in intervals {
let l = interval[0]
let r = interval[1]
if l <= q && q <= r {
let size = r - l + 1
if best == -1 || size < best {
best = size
}
}
}
result.append(best)
}
return result
}
// smoke test
print(minIntervalBruteForce([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5]))
// [3, 3, 1, 4]
print(minIntervalBruteForce([[2,3],[2,5],[1,8],[20,25]], [2,19,5,22]))
// [2, -1, 4, 6]
print(minIntervalBruteForce([], [1,2]))
// [-1, -1]Big-O: O(n * m) time — n intervals scanned for each of m queries. O(1) extra space beyond the output.
Sort intervals by start and process queries in increasing order. Maintain a min-heap of (size, end) pairs for every interval that has started by the current query, ordered by size. Before reading the answer for a query, lazily pop any interval whose end has already passed — it's stale for this query and every later one, since queries only increase from here.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
func minInterval(_ intervals: [[Int]], _ queries: [Int]) -> [Int] {
let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
let sortedQueryIndices = queries.indices.sorted { queries[$0] < queries[$1] }
var answer = [Int](repeating: -1, count: queries.count)
var candidates = Heap<(size: Int, end: Int)>(sort: { $0.size < $1.size })
var i = 0
for queryIndex in sortedQueryIndices {
let q = queries[queryIndex]
// bring in every interval whose start has been reached by this query
while i < sortedIntervals.count && sortedIntervals[i][0] <= q {
let l = sortedIntervals[i][0]
let r = sortedIntervals[i][1]
candidates.insert((size: r - l + 1, end: r))
i += 1
}
// discard intervals that have already ended — stale for this query and every later one
while let smallest = candidates.peek, smallest.end < q {
_ = candidates.extract()
}
if let smallest = candidates.peek {
answer[queryIndex] = smallest.size
}
}
return answer
}
// smoke test — same cases as the brute force
print(minInterval([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5]))
// [3, 3, 1, 4]
print(minInterval([[2,3],[2,5],[1,8],[20,25]], [2,19,5,22]))
// [2, -1, 4, 6]
print(minInterval([], [1,2]))
// [-1, -1]Big-O: O((n + m) log n) time — sorting intervals and queries costs O(n log n) and O(m log m), and each interval/query does at most one O(log n) heap operation. O(n) space for the heap.
The brute force answers each query from a blank slate, rescanning every interval even though most of them were already ruled in or out for the previous query. Sorting queries in increasing order means intervals only ever need to be considered for entry once (when their start is finally reached) and only ever need to be discarded once (when their end is finally passed) — nothing that becomes stale for one query can ever become relevant again for a later one, since queries never go backwards. Keeping the survivors in a min-heap keyed by size means the smallest valid interval for the current query is always sitting at the root, with no need to rescan the whole surviving set every time.
- Heaps and Priority Queues — the min-heap here does real work: keeping the smallest still-valid interval at the root as intervals are added and lazily retired.
- Top K and Heap Pattern — an offline sweep that maintains a heap of "currently eligible" candidates while a sorted secondary sequence (the queries) advances past them.
-
Merge Intervals — the underlying data is the same
[start, end]interval shape as the rest of this category, here paired against a second sorted sequence of query points instead of merged against itself.
Minimum Interval to Include Each Query is the library-shelf sweep — sort the lookups, bring books onto the desk as their coverage begins, retire them once their coverage ends, and always read off the thinnest one still there.
- Why is it safe to permanently discard an interval from the heap once
smallest.end < q, rather than just skipping it for this one query and possibly reconsidering it later? - The heap is ordered by
size, not byend. Walk through why the lazy-deletionwhileloop still correctly discards every stale interval currently in the heap, even though the smallest-by-size interval popped first might not be the one with the earliest end. -
queriesis processed in a different order than it was given (sortedQueryIndices), butansweris written usinganswer[queryIndex]. Why is this necessary, and what would go wrong if the function just appended answers in sorted-query order instead? - Trace the algorithm on
intervals = [[2,3],[2,5],[1,8],[20,25]],queries = [2,19,5,22]. Why does the query19produce-1even though every interval has already been inserted into the heap by the time it's processed?