Why sort the queries?

Answered in increasing order, the set of intervals that have started only grows, and an interval that has ended before one query has ended before every later one. That lets one pointer sweep the intervals by start and lets the heap discard expired intervals for good, so each interval is pushed and popped at most once.

Why is it safe to pop only from the top?

The heap is keyed by size, so an expired interval deeper in the heap does no harm: it is only removed when it reaches the top. Every interval left in the heap has started; the loop pops until the top also has not ended, and that top is the smallest interval containing the query.

How do I return answers in the original order?

Sort the query indexes rather than the values (or store answers in a map keyed by query value) and write each answer to its original position. Duplicate queries get the same answer either way.

What is the time complexity?

Sorting is O(n log n) for the intervals and O(m log m) for the queries. Each interval is pushed once and popped at most once, O(n log n) in total, so the whole algorithm is O(n log n + m log m) with O(n + m) extra space. Checking every interval for every query would be O(n · m).

Minimum Interval to Include Each Query

For each query, find the size of the smallest interval that contains it: answer queries in sorted order with a sweep over starts and a min-heap by size.

HardSolve on LeetCode

Problem Understanding

Minimum Interval to Include Each Query: given intervals[i] = [left, right] (size right − left + 1) and a list of queries, return, for each query, the size of the smallest interval with left ≤ q ≤ right, or -1 if none contains it.

Examples: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] returns [3,3,1,4]; intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] returns [2,-1,4,6].

The Intuition: Answer the Queries in Order

Checking every interval for every query is O(n · m). Sorting turns it into one sweep:

Queries in increasing order mean intervals only ever start, never "unstart". A pointer over intervals sorted by start pushes each one once, when it begins.
A min-heap by size always shows the smallest started interval on top.
Expired intervals leave from the top: if the top ended before this query, it ended before every later query too, so pop it for good. The first top that has not ended is the answer.

The same "sort, sweep, keep the best candidates in a heap" pattern drives Meeting Rooms II, where the heap holds end times, and the heap here works exactly like the one in Kth Largest Element in an Array. More interval problems are in the intervals pattern.

Interactive Walkthrough

DASHED = THE QUERY

SORT, EMPTY HEAP

intervals, sorted by start

[1,4]

[2,4]

[3,6]

[4,4]

query

answers

· · · ·

min-heap (size, end)

Empty

Sort intervals by start: [1,4] [2,4] [3,6] [4,4]. Answer queries smallest first, with an empty min-heap of (size, end)

Query 2: add every interval that has started by 2, drop the ones that ended before it

Free preview: the first 6 of 17 steps

intervals

queries

Intervals are drawn sorted by start, and the dashed line is the query being answered. Tinted intervals are in the heap, the solid one was just pushed or popped, struck-out ones were popped, and the green one is the heap's top: the answer. Try Example 2 to see a query with no answer.

Dry Run Table

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] (already sorted).

Query	Pushed (size, end)	Popped	Top	Answer
2	(4,4) from [1,4], (3,4) from [2,4]	none	(3,4)	3
3	(4,6) from [3,6]	none	(3,4)	3
4	(1,4) from [4,4]	none	(1,4)	1
5	none	(1,4), (3,4), (4,4): all end at 4	(4,6)	4

Answer: [3,3,1,4].

The Solution Template

Sort both sides, push intervals as they start, pop the top while it has ended, read the top.

Minimum Interval to Include Each Query Code

1class Heap {
2    constructor(before) {
3        this.items = [];
4        this.before = before;
5    }
6
7    size() {
8        return this.items.length;
9    }
10
11    peek() {
12        return this.items[0];
13    }
14
15    push(item) {
16        const a = this.items;
17        a.push(item);
18        let i = a.length - 1;
19        while (i > 0 && this.before(a[i], a[(i - 1) >> 1])) {
20            const parent = (i - 1) >> 1;
21            [a[i], a[parent]] = [a[parent], a[i]];
22            i = parent;
23        }
24    }
25
26    pop() {
27        const a = this.items;
28        const top = a[0];
29        const last = a.pop();
30        if (a.length > 0) {
31            a[0] = last;
32            let i = 0;
33            while (true) {
34                const left = 2 * i + 1, right = 2 * i + 2;
35                let first = i;
36                if (left < a.length && this.before(a[left], a[first])) first = left;
37                if (right < a.length && this.before(a[right], a[first])) first = right;
38                if (first === i) break;
39                [a[i], a[first]] = [a[first], a[i]];
40                i = first;
41            }
42        }
43        return top;
44    }
45}
46
47var minInterval = function(intervals, queries) {
48    intervals.sort((a, b) => a[0] - b[0]);
49    const order = queries.map((_, k) => k).sort((a, b) => queries[a] - queries[b]);
50    const heap = new Heap((a, b) => a[0] < b[0]);
51    const ans = new Array(queries.length);
52    let i = 0;
53    for (const k of order) {
54        const q = queries[k];
55        while (i < intervals.length && intervals[i][0] <= q) {
56            const [l, r] = intervals[i];
57            heap.push([r - l + 1, r]);
58            i++;
59        }
60        while (heap.size() > 0 && heap.peek()[1] < q) heap.pop();
61        ans[k] = heap.size() > 0 ? heap.peek()[0] : -1;
62    }
63    return ans;
64};

Edge Cases & Common Mistakes

Sizes are inclusive: [4,4] has size 1, so use right − left + 1.
Losing the original order: sort query indexes, not just values, and write each answer back to its index.
Popping by start: an interval leaves the heap when its end is before the query; its start was already ≤ the query when it was pushed.
Duplicate queries: they get the same answer; with a map keyed by value, the second lookup just reuses it.
No interval covers a query: the heap is empty after popping, so the answer is -1.

Summary

Sort intervals by start and queries by value. For each query, push intervals that have started onto a min-heap of (size, end), pop while the top has ended, and answer with the top's size or -1. O(n log n + m log m) time, O(n + m) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Divide Intervals Into Minimum Number of Groups

Min Arrows to Burst Balloons