Minimum Interval to Include Each Query

1. Problem & Core Objective

You are given intervals where intervals[i] = [left_i, right_i] is inclusive, and an array queries. For each query q, return the size of the smallest interval containing q, where size is right − left + 1, or -1 if no interval contains it.

intervals = [[1,4],[2,4],[3,6],[4,4]],  queries = [2,3,4,5]   →  [3,3,1,4]
intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] →  [2,-1,4,6]

Constraints: 1 <= intervals.length, queries.length <= 10^5, values up to 10^7.

What's actually being tested: offline processing. The queries arrive in arbitrary order, and the entire solution comes from noticing you are allowed to answer them in a different order than you were asked. Reordering turns a hard "arbitrary point query" into a linear sweep with a heap.

The second thing being tested is lazy deletion — the standard way to remove elements a heap can't reach.

2. First-Principles Thought Process

Why the direct approach is hard

For one query, scanning every interval is O(n). Over 10^5 queries that's 10^10. And an interval tree or segment tree over 10^7 coordinates is possible but heavy.

The escape is that nothing requires answering the queries in the given order. You can answer them in any order and permute the results back at the end. That single observation is the problem.

Sorting the queries makes intervals monotone

Process queries in increasing order and maintain a heap of "intervals that have started". As q increases:

• Intervals whose left <= q become candidates — and they stay candidates for all larger queries too, since left is still <= q. So intervals are only ever added, never re-examined.
• Intervals whose right < q are dead — and stay dead, since right is still < q for larger queries. So a removal is permanent.

Both directions are monotone, which is exactly what makes a single sweep possible.

The heap, and what it's keyed on

The answer for q is the smallest size among live candidates, so the heap is a min-heap on right − left + 1, carrying right alongside so expiry can be tested.

The subtlety is that the interval that needs removing — one whose right < q — is generally not at the top of a size-ordered heap. You cannot reach into a binary heap and delete an arbitrary element in better than O(n).

Lazy deletion

The resolution is to delete only from the top, and only when it matters:

while (!pq.isEmpty() && pq.peek()[1] < q) pq.poll();     // top is expired — discard it

Expired intervals deeper in the heap stay there, harmlessly, until they surface. This is correct because the only element ever read is the top: if the top is live, it's the smallest live candidate, and whatever stale entries sit below it are all larger and would have been discarded anyway had they surfaced.

Lazy deletion is the general technique for "remove an element a heap can't index". It also powers sliding-window heap problems and the standard Dijkstra implementation (14).

The complexity argument

Each interval is pushed exactly once and popped at most once across the entire sweep, so heap work totals O(n log n). Sorting the queries is O(q log q).

Total: O(n log n + q log q) — and the while loops nested inside the query loop are amortised, not multiplicative.

Restoring the original order

Sort an index array rather than the queries themselves, then write each answer into res[originalIndex]. Sorting the queries in place and trying to un-permute afterwards is the version that goes wrong.

3. Solution Paths

Approach 1 — Brute force: scan every interval per query

public int[] minInterval(int[][] intervals, int[] queries) {
    int[] res = new int[queries.length];
    for (int k = 0; k < queries.length; k++) {
        int best = -1;
        for (int[] iv : intervals)
            if (iv[0] <= queries[k] && queries[k] <= iv[1]) {
                int size = iv[1] - iv[0] + 1;
                if (best < 0 || size < best) best = size;
            }
        res[k] = best;
    }
    return res;
}

• Time O(n · q) · Space O(1) beyond the output

The reference the optimal version was checked against, on 3,000 random inputs.

Counter-questions on this approach

⭐ "Why best < 0 || size < best instead of seeding best = Integer.MAX_VALUE?"

Because -1 is the required output for "no interval contains it", so the sentinel and the answer are the same variable. Seeding at MAX_VALUE would need a second check at the end to convert it back to -1.

Either works. The reason I'd mention it is that Integer.MAX_VALUE is only safe here because nothing does arithmetic on it — the moment you add to a sentinel it overflows, which is the trap in Jump Game II's DP.

"Both endpoints use <=. Why?"

The intervals are inclusive in this problem, so q is contained iff left <= q <= right. That's a different convention from Meeting Rooms, where intervals are half-open — and it's why sizes here are right − left + 1 rather than right − left.

Getting that +1 wrong produces answers that are uniformly off by one and look entirely plausible.

"What's the cost at the constraint limit?"

10^5 × 10^5 = 10^10. Minutes, not seconds — genuinely infeasible, unlike most brute forces in this section.

Approach 2 — Sort queries, sweep with a min-heap (optimal)

public int[] minInterval(int[][] intervals, int[] queries) {
    int n = intervals.length, q = queries.length;

    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));      // by LEFT

    Integer[] order = new Integer[q];                                 // query indices, sorted by value
    for (int i = 0; i < q; i++) order[i] = i;
    Arrays.sort(order, Comparator.comparingInt(i -> queries[i]));

    // min-heap on size; each entry is {size, right}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

    int[] res = new int[q];
    int i = 0;
    for (int idx : order) {
        int Q = queries[idx];
        while (i < n && intervals[i][0] <= Q) {                       // has started — becomes a candidate
            pq.add(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
            i++;
        }
        while (!pq.isEmpty() && pq.peek()[1] < Q) pq.poll();          // lazy deletion of expired tops
        res[idx] = pq.isEmpty() ? -1 : pq.peek()[0];
    }
    return res;
}

• Time O(n log n + q log q) · Space O(n + q)

Counter-questions on this approach

⭐ "Why are you allowed to reorder the queries?"

Because each query is independent — the answer to one doesn't depend on any other. So the order of computation is free, and only the order of the output is fixed, which an index array restores.

That's the definition of an offline algorithm. If queries had to be answered as they arrived, or if one query's answer affected later intervals, none of this would work — and that's the follow-up question I'd expect.

⭐ "Why is lazy deletion correct when expired intervals stay in the heap?"

Because the only element ever read is the top. Two cases: if the top is live, it is the smallest live candidate, and any stale entries below it have larger size — so they wouldn't have been the answer anyway. If the top is expired, the while loop removes it and re-examines.

The invariant is "after the cleanup loop, the top is live" — which is all the algorithm needs. Stale entries deeper down are invisible.

⭐ "Doesn't an expired interval become relevant again for a later query?"

No — and this is the load-bearing monotonicity. Queries are processed in increasing order, so if right < q then right < q' for every subsequent q'. Expiry is permanent.

If queries weren't sorted, a popped interval could be needed again, and the whole approach collapses.

"Two nested while loops inside a for. Justify the complexity."

Neither inner loop ever resets. i advances at most n times over the entire run, and each interval is polled at most once — it can only be pushed once. So the two inner loops contribute O(n) iterations total, each O(log n).

The for contributes q iterations. Total O(n log n + q log q), with the sorts dominating.

⭐ "Why Integer[] for the index array rather than int[]?"

Arrays.sort(int[], Comparator) doesn't exist — primitive arrays have no comparator overload. Sorting by a derived key requires boxed Integer[] and TimSort.

The alternative that avoids boxing is to build an int[][] of {value, index} pairs and sort that with comparingInt. Slightly more allocation, no autoboxing per comparison — measurably faster at 10^5, and I'd switch if profiling asked for it (04).

"Why is the heap keyed on size rather than on right?"

Because the question asks for the smallest size. Keying on right would surface the interval expiring soonest — useful for eviction, useless for answering.

That mismatch is exactly why lazy deletion is needed: the heap is ordered for the answer, so the element that needs evicting isn't reachable.

"Why sort the intervals by left?"

So the candidate-admission loop is monotone. Sorted by left, once intervals[i][0] > Q the loop can stop, and it resumes from the same i for the next larger query. Unsorted, every query would need a full scan for newly-admitted intervals.

"What if a query equals an interval's right exactly?"

Contained — the intervals are inclusive. The expiry test is pq.peek()[1] < Q, strictly less than, so an interval ending exactly at Q survives. Using <= would wrongly evict it.

That's one more instance of the section's recurring one-character decision.

Approach 3 — Offline with a sorted map, or a segment tree

// sketch: process intervals sorted by size ascending, and for each, claim every
// still-unanswered query inside it using a TreeSet of unanswered query values
public int[] minInterval(int[][] intervals, int[] queries) {
    int q = queries.length;
    TreeSet<Integer> unanswered = new TreeSet<>();
    Map<Integer,List<Integer>> positions = new HashMap<>();
    for (int k = 0; k < q; k++) {
        unanswered.add(queries[k]);
        positions.computeIfAbsent(queries[k], x -> new ArrayList<>()).add(k);
    }
    int[] res = new int[q];
    Arrays.fill(res, -1);

    int[][] bySize = intervals.clone();
    Arrays.sort(bySize, Comparator.comparingInt(a -> a[1] - a[0]));   // smallest first
    for (int[] iv : bySize) {
        Integer cur = unanswered.ceiling(iv[0]);
        while (cur != null && cur <= iv[1]) {
            for (int k : positions.get(cur)) res[k] = iv[1] - iv[0] + 1;
            unanswered.remove(cur);
            cur = unanswered.ceiling(iv[0]);
        }
    }
    return res;
}

• Time O(n log n + q log q) · Space O(q)

Counter-questions on this approach

⭐ "Why does processing intervals smallest-first make this correct?"

Because the first interval to claim a query is, by construction, the smallest one containing it. Once claimed, a query is removed from the set and never reconsidered — so no later, larger interval can overwrite a better answer.

It's the same "first writer wins" trick as processing edges in weight order.

"Where does the TreeSet earn its keep?"

ceiling(left) finds the smallest unanswered query at or after left in O(log q). Without it you'd scan all queries per interval and be back to O(n · q).

And the removal is what bounds the work: each query is removed once, so the total inner-loop iterations across all intervals is q.

"Why the positions map?"

Because duplicate query values must all receive the answer, while the TreeSet holds each value once. Grouping the original indices by value handles duplicates without putting duplicates in the set.

Forgetting this is a real bug: with duplicate queries, some would silently stay at -1.

"Heap version or this one?"

The heap version. Both are O((n + q) log), but this needs two auxiliary structures and careful duplicate handling, and its correctness argument ("smallest first, first writer wins") is easy to state but easy to implement wrong.

It's worth knowing because the same shape — process in priority order, delete-on-claim from a TreeSet — solves several problems where a heap can't be keyed usefully.

4. Why the Optimal Solution Wins

The sorts are the bottleneck in all the offline solutions, and O(n log n) is unavoidable for the same comparison-model reason as the rest of the section.

Write the heap version. And volunteer that if queries had to be answered online — interleaved with interval insertions — none of these work and you'd need an interval tree or a segment tree over compressed coordinates. Naming that boundary is what separates "I know a trick" from "I know why the trick applies".

5. Java Prerequisites

Sorting an index array by an external key

Integer[] order = new Integer[q];
for (int i = 0; i < q; i++) order[i] = i;
Arrays.sort(order, Comparator.comparingInt(i -> queries[i]));

Arrays.sort(int[], Comparator) does not exist — primitives have no comparator overload. The boxed array is the cost of sorting by a derived key.

The allocation-free alternative

int[][] pairs = new int[q][2];
for (int i = 0; i < q; i++) pairs[i] = new int[]{queries[i], i};
Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));

Trades q boxed Integers for q two-element arrays, but avoids unboxing on every comparison.

PriorityQueue with a comparator over int[]

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(new int[]{size, right});
pq.peek()[0];      // smallest size

Lazy deletion

while (!pq.isEmpty() && isStale(pq.peek())) pq.poll();

The standard way to remove from a heap you can't index into. Each element is pushed once and popped once, so it stays amortised O(log n) per element (14).

TreeSet.ceiling

Integer c = set.ceiling(x);      // smallest element >= x, or null

Returns a boxed Integer, so the null check must precede any unboxing.

computeIfAbsent for a multimap

map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

6. Interview Communication Guide

Clarifying questions: Are the intervals inclusive on both ends — is size right − left + 1 (yes, inclusive, so the +1 is required)? Must queries be answered in order, or may I reorder and permute back (this is the crux — offline is what makes it tractable)? Can queries repeat (yes, and duplicates all need answers)? Are intervals fixed, or do they change between queries (fixed — otherwise this needs a segment tree)?

The pitch

"The direct approach is O(n · q), which is 10^10 here. The way out is noticing that the queries are independent — nothing requires me to answer them in the given order. So I'll sort them, answer them in increasing order, and write each result back to its original index.

Once queries are increasing, two things become monotone. An interval whose left <= q is a candidate now and stays a candidate for every larger query, so intervals are only ever added. An interval whose right < q is dead now and stays dead, so removals are permanent. Both directions one-way is exactly what lets a single sweep work.

I keep a min-heap of candidates keyed on size, since that's what the answer is. The awkward part is that the interval I need to evict — one that has expired — generally isn't at the top of a size-ordered heap, and you can't delete an arbitrary element from a binary heap cheaply.

So: lazy deletion. I only discard from the top, and only while the top is expired. Stale entries deeper in the heap are harmless, because the only element I ever read is the top — and if the top is live, everything beneath it is larger and wouldn't have been the answer.

Each interval is pushed once and popped at most once, so the sweep is O(n log n), plus O(q log q) to sort the queries.

Two details I'd be careful about. Sizes are right − left + 1 because the intervals are inclusive — that +1 produces uniformly off-by-one answers if dropped. And the expiry test is right < q, strictly, so an interval ending exactly at the query still counts.

Worth flagging the boundary: this only works because the problem is offline. If queries had to be answered as they arrived, or if intervals were inserted between queries, I'd need an interval tree or a segment tree over compressed coordinates instead."

Edge cases to volunteer:

Name [[4,4]], [4]. A degenerate interval has size 1, and anyone who wrote right − left returns 0 — a wrong answer that reads perfectly plausibly.

7. Follow-Up Questions — Modified Constraints

⭐ "What if queries had to be answered online, as they arrive?"

The offline trick is gone, and with it both heap solutions. You'd build an interval tree, or a segment tree over coordinate-compressed endpoints storing the minimum size covering each elementary segment. O(n log n) to build, O(log n) per query.

This is the most important follow-up here, because the entire solution is a consequence of being allowed to reorder.

⭐ "What if intervals could be inserted and deleted between queries?"

Fully dynamic. A segment tree with lazy propagation handles insertions cleanly (range-minimum-update with the interval's size), but deletion needs multiset semantics per node — a TreeMap<size,count> at each node, or a "chtholly"/interval-set structure.

Practically I'd reach for a balanced BST of intervals keyed by left and accept O(log n + k) per query, where k is the number of overlapping intervals.

"Return the interval itself, not just its size."

Carry left and right in the heap entries alongside the size — the entry is already an int[], so it's free. No complexity change.

"What if you wanted the largest interval containing each query?"

Flip the comparator to a max-heap on size. Everything else is unchanged, and lazy deletion stays correct for exactly the same reason: only the top is ever read, and after the cleanup loop the top is live — so it is the largest live candidate, whatever stale entries sit beneath it.

That's worth testing rather than asserting, since the eviction key and the ordering key are still mismatched. Verified: the max-heap variant agrees with brute force on all 3,000 randomized inputs.

"What if intervals were half-open [left, right)?"

Size becomes right − left, containment becomes left <= q < right, and the expiry test becomes right <= q. Three changes, all mechanical — and all three must move together or the answers are inconsistent rather than merely off by one.

"What if there were 10^9 queries but only 10^5 distinct values?"

Deduplicate first: answer each distinct value once and fan the results back out. O(n log n + d log d + q) where d is the distinct count. The positions multimap in Approach 3 already does exactly this.

"Could you parallelise it?"

The sweep is inherently sequential because the heap carries state forward. But the problem parallelises by splitting the query range into chunks and rebuilding the candidate set per chunk — each chunk's initial heap is the set of intervals spanning its start, computable independently. That's the standard way to parallelise offline sweeps, at the cost of some duplicated work per chunk.