LeetEye LeetEye
Hard Intervals ~5 min

Minimum Interval to Include Each Query

intervals minimum-interval-to-include-each-query

Problem

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 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 lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array answer where answer[j] is the answer to the jth query.

Examples

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

Sort intervals by start and queries by value. Use min-heap of (size, end) to track valid intervals.

Sort intervals by start, queries by value. Sweep: add intervals starting <= query to min-heap (by size), remove expired ones (end < query). Heap top = answer.

How to Approach This Problem

Pattern Recognition: When you see keywords like minimum interval to include each query intervals, think Intervals.

Step-by-Step Reasoning

1 Processing queries in sorted order:
Answer: Allows efficient interval management
Can add intervals as we move right, remove expired ones. Efficient sweeping.
2 The min-heap stores:
Answer: (size, end) pairs
Priority by size (want smallest). Need end to check if still valid.
3 Add interval to heap when:
Answer: Interval start <= current query
If interval starts at or before query, it might contain query. Add to candidates.
4 Remove interval from heap when:
Answer: Its end < current query
If end < query, interval can't contain query (or any future query since sorted).
5 After cleanup, answer is:
Answer: Heap top's size (if heap non-empty)
Min-heap by size, so top is smallest valid interval.

Solution

def minInterval(intervals: List[List[int]], queries: List[int]) -> List[int]:
    # Sort intervals by start
    intervals.sort()
    
    # Sort queries but keep original indices
    sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
    
    result = [-1] * len(queries)
    heap = []  # (size, end)
    i = 0
    
    for idx, q in sorted_queries:
        # Add all intervals that start <= query
        while i < len(intervals) and intervals[i][0] <= q:
            l, r = intervals[i]
            heapq.heappush(heap, (r - l + 1, r))
            i += 1
        
        # Remove expired intervals (end < query)
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        
        # Smallest valid interval
        if heap:
            result[idx] = heap[0][0]
    
    return result

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Intervals problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye