Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    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

    Watch how the sweep and the heap cooperate as the queries climb: the pointer pushes every interval whose start has become small enough, and only the heap top is ever inspected for expiry.

    2idx 0
    3idx 1
    4idx 2
    5idx 3

    Intervals (sorted by start) · swept 0/4

    [1, 4]size 4later
    [2, 4]size 3later
    [3, 6]size 4later
    [4, 4]size 1later

    Min-heap by (size, end)

    empty
    empty
    empty
    empty

    Only the top is guaranteed smallest; entries are shown in key order.

    Answers (by input index)

    ?idx 0
    ?idx 1
    ?idx 2
    ?idx 3
    1 / 9
    currentseenresultdiscarded

    Sort intervals by start and queries by value, then sweep. The pointer walks starts once and the heap holds candidate intervals keyed by (size, end).

    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.

    More Intervals practice