Difficulty: HardIntervals

Minimum Interval to Include Each Query

Problem in Plain English

You are given a list of intervals and a list of query points, and each query asks for the shortest interval covering it. Return those minimum sizes in the original query order, or -1 wherever nothing covers the query.

Problem Statement

You are given a 2D integer array intervals and an integer array queries. For each query point q, find the interval with start <= q <= end that has the smallest size, where size is end - start + 1.

Return an array holding that minimum size per query in the original query order, or -1 for any query no interval contains.

Constraints

There are between 1 and 100000 intervals, and between 1 and 100000 queries.
Each interval has exactly two integer endpoints, start and end.
Endpoints satisfy $1 \leq start \leq end \leq 10^7$ .
Each query is an integer between 1 and 10000000 inclusive.

Examples

Example 1

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]

Query 2 is covered best by [2,4] (size 3); query 3 also by [2,4]; query 4 by [4,4] (size 1); query 5 only by [3,6] (size 4).

Example 2

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

Query 2 fits [2,3] (size 2); query 19 fits nothing (-1); query 5 fits [2,5] (size 4); query 22 fits [20,25] (size 6).

Example 3

Input: intervals = [[4,4]], queries = [5,4,4,3]
Output: [-1,1,1,-1]

Only point 4 is covered, with inclusive size 1. Both copies of query 4 receive their own answer, and answers stay in the original unsorted query order.

Example 4

Input: intervals = [[1,10],[1,3],[1,1]], queries = [1,4,10]
Output: [1,10,10]

At query 1 the singleton wins. At query 4 both shorter intervals have expired, so [1,10] wins with size 10. The endpoint 10 is still included.

Example 5

Input: intervals = [[1,10000000]], queries = [10000000,1]
Output: [10000000,10000000]

The maximum allowed endpoint does not change inclusive arithmetic: the interval contains ten million integer points, and both boundaries are covered.

Intuition

Each query asks for the smallest containing interval, not the nearest endpoint. In Example 1, query 4 belongs to four intervals but the singleton [4,4] wins with size 1. Sorting queries lets us reuse candidate intervals: once their start is reached they become eligible, and once their end is passed they can never help a later query. A minimum heap chooses by interval size, while stored ends let us discard candidates that have expired.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

For each query, inspect every interval and keep the smallest inclusive size among those whose endpoints surround it. This directly expresses the definition and avoids sorting, but repeats a complete interval scan for every query.

Step-by-Step Logic

Allocate an answer array in original query order. For each query, reset best to an infinity sentinel so values from earlier queries cannot leak into the answer.
Scan every interval and test both inclusive boundaries. If it covers the query, update best with end - start + 1. For query 2 in Example 1, [1,4] sets best to 4, then [2,4] lowers it to 3.
After the scan, append best or -1 if the sentinel is unchanged. Example 1 records 3 for query 2.
Repeat independently for all remaining queries. Example 1 finds 3, 1, and 4 for queries 3, 4, and 5, returning [3,3,1,4].

Why It Works

For a fixed query, best is the smallest size of a covering interval seen so far, or the sentinel when none has covered it. A noncovering interval cannot improve that answer. A covering interval replaces best only with the minimum of the old value and its own size, preserving the invariant. After every interval has been considered, best is exactly the required minimum, or no candidate exists and the answer is -1. Repeating this scan in query order gives the required output order, including duplicate queries.

Dry Run

Brute Force: variable states at each step
Query	Interval checked	Covers? / size	Best before → after	Answer after scan
2	[1,4]	yes / 4	infinity → 4	scan continues
2	[2,4]	yes / 3	4 → 3	scan continues
2	[3,6]	no	3 → 3	scan continues
2	[4,4]	no	3 → 3	3
3	[1,4]	yes / 4	infinity → 4	scan continues
3	[2,4]	yes / 3	4 → 3	scan continues
3	[3,6]	yes / 4	3 → 3	scan continues
3	[4,4]	no	3 → 3	3
4	[1,4]	yes / 4	infinity → 4	scan continues
4	[2,4]	yes / 3	4 → 3	scan continues
4	[3,6]	yes / 4	3 → 3	scan continues
4	[4,4]	yes / 1	3 → 1	1
5	[1,4]	no	infinity → infinity	scan continues
5	[2,4]	no	infinity → infinity	scan continues
5	[3,6]	yes / 4	infinity → 4	scan continues
5	[4,4]	no	4 → 4	4
end	all scans complete	-	-	return [3,3,1,4]

Complexity Analysis

Time Complexity

O(nm)

Space Complexity

O(m)

Let n be the number of intervals and m the number of queries. Each of m queries checks all n intervals, giving O(nm) time, up to ten billion checks at the maximum bounds. The returned answer array occupies O(m) space; auxiliary storage excluding that output is O(1). Inputs are read without sorting, copying, or mutation. Inclusive sizes are at most 10000000, safely within Java int and exact JavaScript integer arithmetic.

Code

Solution.java

1class Solution {2    public int[] minInterval(int[][] intervals, int[] queries) {3        int[] res = new int[queries.length];4        for (int i = 0; i < queries.length; i++) {5            // Reset per query; the sentinel distinguishes no cover from any real size.6            int best = Integer.MAX_VALUE;7            for (int[] in : intervals) {8                if (in[0] <= queries[i] && queries[i] <= in[1]) {9                    // Both endpoints count, so singleton intervals have size one.10                    best = Math.min(best, in[1] - in[0] + 1);11                }12            }13            res[i] = best == Integer.MAX_VALUE ? -1 : best;14        }15        return res;16    }17}

Hints

Hint 1

Answering each query from scratch repeats the same interval scans many times.

Hint 2

Sorting the queries lets one left-to-right pass feed every interval into a shared structure exactly once.

Hint 3

Keep active intervals in a heap ordered by size, and evict any whose end falls short of the current query before reading the top.

Edge Cases

A singleton [4,4] covers only query 4 and has size 1.
A query equal to either interval endpoint is covered; expiry uses end < query.
Queries with no covering interval return -1, including a gap between otherwise disjoint intervals.
Duplicate query values need separate answer slots; unsorted queries must retain their original order.
Nested intervals and equal-size candidates are common: shortest size wins, not earliest start or latest end.
At maximum bounds, [1,10000000] has size 10000000; all size and comparator arithmetic fits the shown integer types.

Common Mistakes and Interview Tips

Computing end - start instead of end - start + 1 returns zero for a singleton and undercounts every interval.
Sorting the caller’s interval array in place changes its order. These snippets sort an outer copy and never modify rows.
Ordering the heap by end instead of size returns the earliest-expiring interval, which need not be the shortest.
Removing entries with end <= query loses intervals that cover their right endpoint.
Returning the sorted-query answers without original indices mishandles unsorted and duplicate queries.
Removing only one expired root is insufficient: the next root may also be stale, as query 5 in Example 1 shows.
Claiming the entire heap contains only active intervals is false. State the useful invariant precisely: after cleanup, its root is the smallest valid candidate; expired buried entries may remain.
Interview tip: explain why sorting queries makes discarded intervals permanently irrelevant, and why each interval is inserted and removed at most once.

Key Takeaway

When queries can be reordered internally, sort them to make candidate eligibility monotone, then use a heap keyed by the requested optimum and lazy expiry at the root. Store original indices to restore the external answer order.