Minimum Interval to Include Each Query

You are given a 2D integer array intervals where intervals[i] = [left_i, right_i] represents the inclusive interval [left_i, right_i], and a 1D integer array queries. For each query queries[j], find the size of the smallest interval [left_i, right_i] such that left_i <= queries[j] <= right_i. The size of an interval is right_i - left_i + 1. If no interval contains the query, the answer is -1.

This is LeetCode 1851: Minimum Interval to Include Each Query, a hard problem that combines sorting, sweep-line processing, and a min-heap into a single clean solution. Once you see the pattern, the implementation is compact.

Why this problem matters

This problem is a textbook example of the offline query pattern: instead of answering each query independently, you sort the queries and process them together with the data. This transforms a brute-force O(n * q) approach into an efficient O((n + q) log n) one.

The same pattern appears whenever you have a batch of queries against a dataset. Sorting both lets you sweep through them in tandem, adding and removing elements as you go. You will see this idea in problems involving intervals, ranges, and event-based processing. Meeting Rooms II uses a similar heap-based approach with sorted intervals.

The brute force approach

The most direct solution checks every interval for every query.

def min_interval_brute(intervals, queries):
    result = []
    for q in queries:
        best = -1
        for left, right in intervals:
            if left <= q <= right:
                size = right - left + 1
                if best == -1 or size < best:
                    best = size
        result.append(best)
    return result

For each of the q queries, you scan all n intervals. That is O(n * q), which is far too slow when both n and q can reach 10^5.

The key insight

If you sort the queries and process them in ascending order, you can maintain a heap of "active" intervals. As queries increase, you add new intervals whose start is <= the current query, and you lazily remove intervals whose end is < the current query. The heap top always holds the smallest active interval.

Walking through it step by step

Let's trace through intervals = [[1,4],[2,4],[3,6],[4,4]] and queries = [2,3,4,5]. The sorted intervals by start are [[1,4],[2,4],[3,6],[4,4]]. The sorted queries (with original indices) are [(2,0),(3,1),(4,2),(5,3)]. The heap stores (size, end) tuples.

Notice how the heap grows as we encounter new intervals and shrinks as old intervals expire. We never rescan intervals we have already added. Each interval enters the heap once and leaves at most once.

The solution

import heapq

def min_interval(intervals, queries):
    intervals.sort()
    sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
    result = [-1] * len(queries)
    heap = []
    i = 0

    for orig_idx, q in sorted_queries:
        while i < len(intervals) and intervals[i][0] <= q:
            left, right = intervals[i]
            heapq.heappush(heap, (right - left + 1, right))
            i += 1

        while heap and heap[0][1] < q:
            heapq.heappop(heap)

        if heap:
            result[orig_idx] = heap[0][0]

    return result

Here is what each piece does:

1. Sort intervals by start time. This lets us add them in order as queries sweep left to right.
2. Sort queries by value, preserving original indices. We need to fill the result array in the original query order, so we pair each query with its index before sorting.
3. For each query, add all intervals whose start <= the query. We push (size, end) onto the heap. The size is right - left + 1.
4. Remove expired intervals. While the heap top has an end value < the current query, pop it. These intervals no longer contain the query point.
5. Read the answer. If the heap is not empty, the top element has the smallest size among all active intervals. Otherwise, the answer is -1.

Complexity analysis

Sorting intervals takes O(n log n). Sorting queries takes O(q log q). Each interval is pushed and popped from the heap at most once, with each operation costing O(log n). The total heap work is O(n log n). Iterating through queries is O(q). Overall: O((n + q) log(n + q)), which simplifies to O((n + q) log n) when n and q are comparable.

Building blocks

This problem combines two reusable patterns that CodeBricks drills independently.

1. Offline query processing

When you have a batch of queries to answer against a dataset, sorting both and sweeping through them together is often more efficient than answering each query independently. The template looks like this:

data.sort(key=sort_key)
sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
result = [default] * len(queries)
j = 0

for orig_idx, q in sorted_queries:
    while j < len(data) and should_add(data[j], q):
        add_to_structure(data[j])
        j += 1
    result[orig_idx] = query_structure(q)

The critical detail is preserving original indices. You sort queries for processing efficiency, but you write answers back to the original positions. Forgetting this is a common mistake.

2. Lazy deletion from a heap

Python's heapq does not support removing arbitrary elements. Instead of removing expired entries eagerly, you leave them in the heap and pop them lazily when they bubble to the top. Before reading the heap top, check if it is still valid:

while heap and not is_valid(heap[0]):
    heapq.heappop(heap)

This lazy deletion pattern is used in many heap-based problems. Each element is pushed once and popped once, so the total work stays O(n log n) even though invalid elements may linger in the heap temporarily.

Edge cases

Before submitting, make sure your solution handles these:

• No interval contains a query. If intervals = [[1,2]] and queries = [5], the answer is [-1]. After adding the interval, the heap pops it immediately because end=2 is < 5.
• Multiple intervals, same size. If two intervals both have the smallest size for a query, it does not matter which one you pick. The heap handles this naturally.
• Single-point intervals. [4,4] has size 1. This is the smallest possible interval and only matches query 4 exactly.
• All queries identical. If every query is the same value, you still sort and process correctly. All intervals get added in one batch, expired entries get cleaned, and you read the same heap top for each.
• Intervals and queries with large values. The algorithm depends on sorting, not on value ranges, so it handles values up to 10^7 without issues.

From understanding to recall

You have seen the sweep-line approach: sort intervals, sort queries, push/pop from a heap. The logic is clean. But in an interview, the details are where things go wrong. Do you push (size, end) or (end, size)? Do you check heap[0][1] < q or <= q? Do you sort queries by value or by index?

These small decisions determine whether your code passes. Reading through the solution once gives you understanding, but it does not give you the ability to write it from scratch under pressure. Spaced repetition bridges that gap. You practice writing the heap loop, the query sorting with enumerate, and the lazy deletion check until they are automatic.

The offline query pattern and lazy heap deletion are two of the roughly 60 building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems.

Related posts

• Insert Interval - Another interval problem where sorted order and a sweep-based approach simplify the logic
• Meeting Rooms II - Uses sorted intervals with a min-heap to track active meetings, the same heap pattern used here
• Kth Largest Element - Heap-based selection, drilling the min-heap building block from a different angle

CodeBricks breaks LeetCode 1851 into its offline query processing and lazy heap deletion building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sweep-line heap question shows up in your interview, you do not think about it. You just write it.