Minimum Interval to Include Each Query

Solving tips

Go OFFLINE: sort queries ascending (and intervals by left), sweep once, then map answers back to the original query order at the end.
As q grows, admit intervals with left <= q via a pointer into a min-heap keyed by (size, right); the heap key must be interval SIZE, the quantity you minimize, not right.
Discard dead intervals lazily: pop while heap top's right < q right before reading the answer; each interval is pushed and popped at most once for O((n+q) log(n+q)).
Pitfalls: size is right - left + 1 (closed), eviction test is strict '<' (right == q still contains q), and deduping queries handles repeats for free.

Problem

You are given a list of closed intervals [left, right] and a list of integer queries. For each query value q, find the size of the smallest interval that contains q, where an interval’s size is right - left + 1 and “contains” means left <= q <= right. If no interval contains q, the answer for that query is -1. Return the answers in the same order as the queries.

Examples

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] → [3,3,1,4] — e.g. query 4 fits inside [4,4], size 1; query 5 only fits [3,6], size 4.
intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] → [2,-1,4,6] — query 19 lies in a gap, so -1; query 22 fits only [20,25], size 6.

Constraints

1 <= len(intervals), len(queries) <= 10^5
1 <= left <= right <= 10^7
1 <= queries[i] <= 10^7

Both lists reach 10^5, so the O(n * q) scan-per-query is ~10^10 operations — the expected solution is O((n + q) log(n + q)).

Think about it first

Hint 1

Nothing forces you to answer the queries in the order given. What becomes easier if you process them in sorted order and map answers back at the end?

Hint 2

Sweeping queries in increasing order, an interval becomes relevant once its left end is ≤ the query, and becomes dead forever once its right end is < the query. What structure lets you hold the currently relevant intervals and grab the smallest one fast — even with dead ones mixed in?

Hint 3

Sort intervals by left and queries ascending. For each query: push every interval whose left ≤ q into a min-heap keyed by (size, right); then pop from the top while the top's right < q (lazily discarding dead intervals); the surviving top's size is the answer. Each interval is pushed and popped at most once across the whole sweep.

TL;DR

Sort intervals and queries, sweep with a min-heap keyed by interval size — O(n log n + q log q) time, O(n + q) space.

Approach 1 — Brute force: scan all intervals per query

For each query, walk the whole interval list, track the smallest size among intervals that contain it.

from typing import List

class Solution:
    def minInterval(
        self, intervals: List[List[int]], queries: List[int]
    ) -> List[int]:
        answers: List[int] = []
        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
            answers.append(best)
        return answers

Complexity: O(n * q) time, O(q) space for the output.

With n = q = 10^5 that is ~10^10 containment checks — hours in Python. The waste is obvious: consecutive queries mostly see the same set of containing intervals, and the brute force rediscovers it from scratch every time.

Approach 2 — Sort both + min-heap keyed by size (offline sweep)

The insight: answer the queries offline — sorted ascending, restoring the original order at the end. As the query value only ever grows, each interval has a simple life cycle: it enters consideration when the query reaches its left end, and dies permanently once the query passes its right end. So sweep queries in order, admit intervals by left endpoint with a pointer, and keep the live ones in a min-heap ordered by size. Dead intervals need no eager cleanup: discard them lazily, popping only while the heap’s top has right < q — anything buried deeper gets evicted when (and if) it ever surfaces.

Storing (size, right) in the heap means the top is always the smallest live candidate, and its right is right there for the death test.

import heapq
from typing import List

class Solution:
    def minInterval(
        self, intervals: List[List[int]], queries: List[int]
    ) -> List[int]:
        intervals.sort(key=lambda it: it[0])
        answer_for: dict[int, int] = {}
        heap: List[tuple[int, int]] = []  # (size, right) of live intervals
        i, n = 0, len(intervals)

        for q in sorted(set(queries)):
            # Admit every interval that has started by q.
            while i < n and intervals[i][0] <= q:
                left, right = intervals[i]
                heapq.heappush(heap, (right - left + 1, right))
                i += 1
            # Lazily evict intervals that ended before q.
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            answer_for[q] = heap[0][0] if heap else -1

        return [answer_for[q] for q in queries]

Deduplicating with sorted(set(queries)) and a dict handles repeated queries for free — the same value always has the same answer — and the final list comprehension restores the input order.

Walkthrough on intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]:

Sorted intervals: [[1,8],[2,3],[2,5],[20,25]]. Sorted unique queries: [2, 5, 19, 22].

q = 2: admit [1,8] (size 8), [2,3] (size 2), [2,5] (size 4). Heap top is (2, 3); 3 >= 2, alive → answer 2.
q = 5: nothing new to admit (20 > 5). Top (2, 3) has 3 < 5 → pop. New top (4, 5) has 5 >= 5, alive → answer 4.
q = 19: nothing to admit. Top (4, 5) dead → pop; (8, 8) dead → pop. Heap empty → answer -1.
q = 22: admit [20,25] (size 6). Top (6, 25) alive → answer 6.
Map back to original order [2, 19, 5, 22] → [2, -1, 4, 6]. Matches the expected output.

Complexity: sorting costs O(n log n + q log q); across the entire sweep each interval is pushed once and popped at most once (O(n log n) heap work total, thanks to the lazy deletion). Total O((n + q) log(n + q)) time, O(n + q) space.

Variant worth knowing: the same offline idea works with a sorted list of interval sizes plus binary-searchable events, or with a segment tree over coordinates (“paint” each interval’s range with min-size). The heap sweep is the version interviewers expect — least machinery for the same bound.

Common pitfalls

Evicting dead intervals before admitting new ones is fine, but answering before evicting is not — the heap top must be validated against the current q right before you read it.
Keying the heap by right (end time) instead of by size — Meeting Rooms habits. Here the question at the top of the heap is “smallest size still alive?”, so size must be the primary key; right rides along only for the death test.
Forgetting to restore the original query order (or mishandling duplicate queries) — the sweep requires sorted queries, but the caller expects answers positionally.
Computing size as right - left instead of right - left + 1 — these are closed intervals; [4,4] has size 1, not 0.
Popping dead intervals with heap[0][1] <= q — an interval whose right end equals the query still contains it; the eviction test is strictly <.

Pattern takeaway

When many queries hit the same set of intervals, go offline: sort the queries, sort the intervals, and sweep once, admitting intervals with a pointer and retiring them lazily from a heap. The heap’s sort key should be the quantity the question asks to minimize (here interval size), while the sweep’s own ordering handles time. This admit/expire sweep generalizes to most “for each query, best interval covering it” problems.