⚡Flashcard Drill➔
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

  1. Sort the queries but remember their original indices, then sweep the queries in increasing order.
  2. 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.
  3. 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.
  4. 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 with right == q does contain q, so the pop condition is strict right < 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems