Minimum Interval to Include Each Query — Offline Sweep with a Min-Heap

Problem Statement

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] represents the interval [left_i, right_i]. You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. The size of an interval is right_i - left_i + 1. If no such interval exists, return -1.

Constraints:

1 <= intervals.length <= 10^5
1 <= queries.length <= 10^5
queries[i] and interval endpoints are in [1, 10^7]

Examples:

Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation:
  Query 2: intervals [1,4] (size 4) and [2,4] (size 3) contain it. Min size = 3.
  Query 3: intervals [1,4],[2,4],[3,6] contain it. Min size = 3.
  Query 4: [1,4],[2,4],[3,6],[4,4] contain it. Min size = 1 ([4,4]).
  Query 5: only [3,6] contains it. Size = 4.
 
Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]

Why This Problem Matters

Minimum Interval to Include Each Query is a hard problem that combines three important techniques: offline query processing, event-based sweeping, and min-heap with lazy cleanup. Google and Meta use this problem in senior interviews to test whether candidates can recognize when online (one-at-a-time) query processing should be replaced by offline batch processing.

The key insight — that sorting both queries and intervals by position enables a linear sweep — is a fundamental technique in computational geometry and database query optimization. It's used in interval tree queries, range tree lookups, and spatial join algorithms.

Amazon uses variants of this problem in their supply chain optimization systems: "Which smallest delivery window covers each shipment deadline?" is a direct business analog. The ability to answer thousands of such queries efficiently is essential in real-time logistics software.

The problem also teaches the "offline is better" mindset: sometimes batching queries and processing them in sorted order dramatically outperforms answering them one by one. This perspective is crucial for designing efficient database engines, search systems, and analytics pipelines.

The Core Insight

Why process queries offline? If we answer queries one by one, for each query we'd need to search all intervals to find which ones cover it, then find the smallest. This is O(queries × intervals) = O(n²).

The offline insight: Sort queries in increasing order of value. Sort intervals by their left endpoint. Now sweep left to right:

When the sweep reaches a query value q, add all intervals with left <= q to the heap (they're candidates for q).
Remove intervals from the heap whose right < q (they don't cover q).
The answer for q is the smallest interval at the top of the heap.

The heap is ordered by interval size (smaller is better), not by endpoint. This lets us efficiently find the minimum-size covering interval.

Why lazy deletion of expired intervals? An interval is "expired" for query q if right < q. Rather than proactively removing them, pop-and-check them lazily when they rise to the top. This is simpler and equally efficient.

Visual Dry Run

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
 
Sort intervals by left:    [(1,4), (2,4), (3,6), (4,4)]
Sort queries (with idx):   [(2,0), (3,1), (4,2), (5,3)]
result = [-1,-1,-1,-1]
 
Sweep:
i=0, query=2:
  Add intervals with left<=2: [1,4](size=4), [2,4](size=3).
  heap: [(3,4), (4,4)]  ← (size, right)
  Pop expired (right<2): none.
  Heap top = (3, 4). right=4 >= 2. result[0] = 3.
 
i=1, query=3:
  Add intervals with left<=3: [3,6](size=4).
  heap: [(3,4), (4,4), (4,6)]
  Pop expired (right<3): none.
  Heap top = (3, 4). result[1] = 3.
 
i=2, query=4:
  Add intervals with left<=4: [4,4](size=1).
  heap: [(1,4), (3,4), (4,4), (4,6)]
  Pop expired (right<4): none.
  Heap top = (1, 4). right=4 >= 4. result[2] = 1.
 
i=3, query=5:
  No new intervals (all have left<=4 already added).
  heap: [(1,4), (3,4), (4,4), (4,6)]
  Pop expired: (1,4): right=4 < 5 → expired. Pop.
              (3,4): right=4 < 5 → expired. Pop.
              (4,4): right=4 < 5 → expired. Pop.
              (4,6): right=6 >= 5 → keep.
  Heap top = (4, 6). result[3] = 4.
 
Restore original order: result = [3,3,1,4]. ✓

Solution (Optimal)

import heapq
 
def minInterval(intervals, queries):
    # Sort intervals by starting point
    intervals.sort()
    
    # Sort queries but keep original indices to restore order
    sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
    
    result = [-1] * len(queries)
    heap = []  # (size, right_endpoint)
    i = 0  # pointer into intervals
    
    for orig_idx, q in sorted_queries:
        # Add all intervals that start at or before q
        while i < len(intervals) and intervals[i][0] <= q:
            left, right = intervals[i]
            size = right - left + 1
            heapq.heappush(heap, (size, right))
            i += 1
        
        # Remove intervals that have expired (end before q)
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        
        # The smallest remaining interval that covers q
        if heap:
            result[orig_idx] = heap[0][0]
    
    return result

function minInterval(intervals, queries) {
    // Sort intervals by left endpoint
    intervals.sort((a, b) => a[0] - b[0]);
    
    // Sort queries with original indices
    const sortedQ = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
    
    const result = new Array(queries.length).fill(-1);
    
    // Min-heap as sorted array: [size, right]
    const heap = [];
    const heapPush = ([size, right]) => {
        let lo = 0, hi = heap.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (heap[mid][0] < size || (heap[mid][0] === size && heap[mid][1] < right))
                lo = mid + 1;
            else hi = mid;
        }
        heap.splice(lo, 0, [size, right]);
    };
    
    let iInterval = 0;
    
    for (const [q, origIdx] of sortedQ) {
        // Add all intervals starting at or before q
        while (iInterval < intervals.length && intervals[iInterval][0] <= q) {
            const [left, right] = intervals[iInterval++];
            heapPush([right - left + 1, right]);
        }
        
        // Remove expired intervals (end before q)
        while (heap.length && heap[0][1] < q) heap.shift();
        
        // Answer: smallest valid interval
        if (heap.length) result[origIdx] = heap[0][0];
    }
    
    return result;
}

Complexity Analysis:

Time: O((n + q) log n) — sorting intervals O(n log n), sorting queries O(q log q), each interval enters/leaves heap once O(log n)
Space: O(n + q) — heap and sorted query arrays

Common Mistakes

Processing queries online (in original order). The algorithm only works if queries are processed in sorted order. You must sort queries and save original indices to restore the answer order.
Removing expired intervals proactively. You don't need to scan the whole heap for expired intervals — just pop from the top until a valid interval is found. Expired intervals sink to the top when they have the smallest size among expired ones... actually they don't. Wait: we remove when right < q. Since heap is sorted by size not by right, we need to pop all heap entries where right < q. This can be O(n) in the worst case but is amortized O(1) per interval since each is removed at most once.
Off-by-one in size calculation. The size of interval [l, r] is r - l + 1, not r - l.
Forgetting to sort intervals. Without sorting intervals by left endpoint, the sweep pointer i doesn't work correctly.
Initializing result with 0 instead of -1. Queries with no covering interval should return -1, not 0.

Follow-up Questions

How would you modify the algorithm to find the largest (instead of smallest) covering interval?
What if queries can ask for the number of intervals covering each query point? (Count instead of min size.)
What if intervals can be updated (insertion/deletion) between queries? Can you still use offline processing?
Prove that the algorithm correctly handles duplicate interval sizes and endpoints.
What is the maximum number of intervals a single query can be covered by? Does this affect complexity?
Can you solve this with a segment tree instead? What would the complexity be?

LeetCode 56 — Merge Intervals: Sort intervals and merge overlapping ones; foundational interval problem.
LeetCode 57 — Insert Interval: Insert a new interval into sorted non-overlapping intervals.
LeetCode 2263 — Make Array Non-Decreasing or Non-Increasing: Offline processing with sorted sweep.
LeetCode 2406 — Divide Intervals Into Minimum Number of Groups: Interval scheduling with sweepline.
LeetCode 1851 — Minimum Interval to Include Each Query: This exact problem.
LeetCode 218 — The Skyline Problem: Sweep line + heap; classic interval processing pattern.

Key Takeaways

Process queries offline by sorting both intervals (by left) and queries (by value) to enable a linear sweep
The heap stores (size, right) tuples ordered by size — the smallest valid interval is always at the top
Add intervals to the heap as the sweep pointer reaches their left endpoint
Lazily remove expired intervals (right < current query) by popping from the top until the heap top is valid
Save original query indices to restore answer order after processing sorted queries
Time O((n + q) log n), space O(n + q) — each interval enters and leaves the heap exactly once
The offline query + sweep + lazy-heap pattern applies to any "find minimum covering interval for each query" problem

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Common Mistakes#

Follow-up Questions#

Related Problems#

Key Takeaways#

Related reading