DSAPrep
HardIntervals

Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the ith interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as the number of integers it contains, or more formally right_i - left_i + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: Query 2 -> [2,4] has size 3. Query 3 -> [2,4] has size 3. Query 4 -> [4,4] has size 1. Query 5 -> [3,6] has size 4.

Example 2

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: Query 2 -> [2,3] has size 2. Query 19 -> no interval contains it. Query 5 -> [2,5] has size 4. Query 22 -> [20,25] has size 6.

Constraints

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= left_i <= right_i <= 10^7
  • 1 <= queries[j] <= 10^7
View original on LeetCode ↗

Brute Force (Scan Every Interval Per Query)

Time O(n · q)Space O(1)

For each query, scan every interval and track the smallest one that contains it.

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

With n intervals and q queries this costs O(n · q), which is far too slow at the given limits (both up to 10^5). Processing queries in sorted order would let intervals be added and discarded incrementally instead of rescanned every time.

Sort + Min-Heap Sweep

OptimalTime O((n + q) log n)Space O(n + q)

Sort intervals by start, and process queries in increasing order (remembering each query’s original index so the answer can be placed back correctly). Sweep a pointer through the sorted intervals: for the current query q, push every interval whose start is <= q onto a min-heap keyed by (size, end). Because queries only increase, once an interval’s end < q it can never satisfy any future query either — pop those off the top of the heap. Whatever remains on top of the heap is the smallest interval that still covers q.

import heapq


class Solution:
    def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:
        intervals.sort(key=lambda iv: iv[0])
        result = [-1] * len(queries)
        order = sorted(range(len(queries)), key=lambda i: queries[i])


        heap = []  # (size, end)
        i = 0
        for qi in order:
            q = queries[qi]
            while i < len(intervals) and intervals[i][0] <= q:
                left, right = intervals[i]
                heapq.heappush(heap, (right - left + 1, right))
                i += 1
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            if heap:
                result[qi] = heap[0][0]
        return result

Tracing intervals = [[1,4],[2,4],[3,6],[4,4]] (sorted by start) against queries = [2,3,4,5] (already increasing):

Sorted intervals

[1, 4]
[2, 4]
[3, 6]
[4, 4]
1 / 4
merging

Query 2: push every interval starting at or before 2 -> [1,4] (size 4) and [2,4] (size 3). Nothing to expire. Heap top: [2,4], size 3. Answer for query 2 is 3.

Why processing queries in sorted order works: once the sweep pointer passes an interval’s start, it will never need to reconsider it, and once an interval’s end falls behind the current query it can never cover any later (larger) query either — so both the push and the expire steps are monotonic and each interval enters and leaves the heap at most once. Complexity: sorting intervals and queries costs O(n log n + q log q), and each interval is pushed/popped from the heap at most once (O(log n) each) → O((n + q) log n) time; the heap and index bookkeeping use O(n + q) space.