Minimum Interval to Include Each Query

HARD✓ CHIP-TIMEDLC #1851 — FULL STATEMENT ↗

The drill: A shelf of ranges and a list of single points. For each point, find the smallest range that contains it and report that range's length — or -1 if nothing covers it.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two lists arrive together: a shelf of ranges, each spanning from some start value to some end value, and a separate list of single query points.

For every query point, the drill is to find whichever range actually contains that point — start to end, inclusive — and is the smallest of all the ranges that do. The size reported is the range's own length, not anything about the point itself.

When no range on the shelf covers a query point at all, that query's answer is -1. The output lines up one answer per query, in the same order the queries were given.

EX 01

intervals = [[2, 5], [3, 5], [4, 8], [5, 5]] · queries = [3, 4, 5, 6]

→ [3, 3, 1, 5]

SHRINKING BEST ANSWER AS THE QUERY MOVES

EX 02

intervals = [[1, 3]] · queries = [0, 1, 2, 3, 4]

→ [-1, 3, 3, 3, -1]

SINGLE INTERVAL, QUERIES FALL OUTSIDE ON BOTH SIDES

EX 03

intervals = [[1, 10], [2, 3], [4, 6]] · queries = [2, 5, 9]

→ [2, 3, 10]

NESTED INTERVALS, TIGHTEST ONE WINS EACH TIME

up to tens of thousands of intervals and queries in one call
interval and query values are non-negative integers
an interval's end is never before its own start; containment includes both endpoints
a query with no covering interval reports -1

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking every interval against every query is the honest baseline. Sorting both intervals and queries opens up a sweep — but you also need 'currently active intervals, smallest first' answered fast at any moment. What structure keeps that cheap?

HINT 2 THE STRUCTURE

Sort queries ascending and intervals by start. Sweep the queries left to right, pushing every interval whose start is at or before the current query into a min-heap keyed by interval size — that heap now holds every interval that COULD cover this query.

HINT 3 ONE STEP FROM THE ANSWER

Before answering a query, pop heap entries whose interval end is before the query — they can never cover this or any later query. Whatever survives on top of the heap is the smallest interval still alive, and it covers this query because its start already passed and its end just did too.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SIZE-HEAP SWEEPPATTERN · SWEEP + MIN-HEAPintervals = [[2,5],[3,5],[4,8],[5,5]] · queries = [3, 4, 5, 6]

[2,5]

[3,5]

[4,8]

[5,5]

HEAP (size, end) — smallest size on top

— empty —

STEP 1

Intervals sorted by start: [2,5],[3,5],[4,8],[5,5]. Queries [3,4,5,6]. Push intervals as their start arrives, then read the smallest one still covering the query.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/minimum-interval-to-include-each-query.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        ordered = sorted(intervals)
        order = sorted(range(len(queries)), key=lambda idx: queries[idx])

        result = [-1] * len(queries)
        heap = []  # (size, end)
        i, n = 0, len(ordered)

        for qi in order:
            q = queries[qi]
            while i < n and ordered[i][0] <= q:
                l, r = ordered[i]
                heapq.heappush(heap, (r - l + 1, r))
                i += 1
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            if heap:
                result[qi] = heap[0][0]

        return result

TIME O((N+M) LOG N)SPACE O(N+M)PYTHON · RACE PACE · 21 LN

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        result = []
        for q in queries:
            best = -1
            for l, r in intervals:
                if l <= q <= r:
                    size = r - l + 1
                    if best == -1 or size < best:
                        best = size
            result.append(best)
        return result

TIME O(N·M)SPACE O(1)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[][] ordered = intervals.clone();
        Arrays.sort(ordered, (a, b) -> Integer.compare(a[0], b[0]));

        int m = queries.length;
        Integer[] order = new Integer[m];
        for (int i = 0; i < m; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));

        int[] result = new int[m];
        Arrays.fill(result, -1);
        // heap holds {size, end}, smallest size on top
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

        int i = 0, n = ordered.length;
        for (int qi : order) {
            int q = queries[qi];
            while (i < n && ordered[i][0] <= q) {
                int l = ordered[i][0], r = ordered[i][1];
                heap.add(new int[] { r - l + 1, r });
                i++;
            }
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll();
            }
            if (!heap.isEmpty()) {
                result[qi] = heap.peek()[0];
            }
        }
        return result;
    }
}

TIME O((N+M) LOG N)SPACE O(N+M)JAVA · RACE PACE · 33 LN

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

TIME O(N·M)SPACE O(1)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED