NeetCode #847LC-1851HardIntervalsNC 150NC 250
← Back to All Problems#847 · #1851 · Minimum Interval to Include Each Query(包含每个查询的最小区间)
📌 Problem Statement & Constraints
You are given a 2D array
intervals, where intervals[i] = [left, right], and an array queries. For each query q, find the length of the smallest interval containing q (i.e. left <= q <= right), or -1 if no interval contains it. Return an array of answers in the original query order. Constraints: 1 <= intervals.length, queries.length <= 10^5, 1 <= left <= right <= 10^7, 1 <= queries[i] <= 10^7.💡 Core Algorithmic Approaches
- Sort the queries but remember their original indices, then sweep the queries in increasing order.
- Sort the intervals by left endpoint and add every interval whose left is at most the current query into a min-heap keyed by length.
- Pop the heap top while its right endpoint is smaller than the query -- such intervals can never contain this query or any later (larger) one.
- The heap top is then the shortest interval containing the query; this offline sweep works because queries only move rightward.
💻 Benchmark Python3 Implementation
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
import heapq
intervals.sort()
order = sorted(range(len(queries)), key=lambda i: queries[i])
res = [-1] * len(queries)
heap = [] # (length, right endpoint)
j = 0
for qi in order:
q = queries[qi]
while j < len(intervals) and intervals[j][0] <= q:
l, r = intervals[j]
heapq.heappush(heap, (r - l + 1, r))
j += 1
while heap and heap[0][1] < q:
heapq.heappop(heap) # cannot contain q or anything larger
if heap:
res[qi] = heap[0][0]
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + q) log n): each interval is pushed once and each query does a heap cleanup.
💾 Space Complexity
O(n + q): the heap and the answer array.
⚠️ Interview Pitfalls & Follow-ups
- Answering queries in input order: the offline sweep requires increasing query values, so queries must be sorted with their indices tracked.
- Popping on
heap[0][1] <= q: an interval withright == qdoes containq, so the pop condition is strictright < q. - Re-scanning all intervals per query: that is O(n * q) and times out; the heap makes each interval enter and leave at most once.
- Storing the interval instead of its length in the heap: the heap must be keyed by length so the top is the shortest containing interval.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.