We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Interval to Include Each Query

Number: 1977

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given a list of intervals where each interval is defined by its start and end (inclusive), and a list of query integers, determine for each query the size of the smallest interval that contains the query. The size of an interval is measured as (right - left + 1). If no interval contains the query, return -1 for that query.

Key Insights

  • Sort the intervals by their start values to efficiently determine when an interval becomes relevant for a given query.
  • Process queries in increasing order so that intervals can be added to a data structure (min-heap) as they "start" to cover queries.
  • Use a min-heap keyed by the size (length) of the interval to quickly retrieve the smallest interval currently containing the query.
  • Remove any intervals from the heap that no longer cover the current query (i.e., their end is less than the query).
  • Maintain the original order of queries by storing the indices while sorting.

Space and Time Complexity

Time Complexity: O((N + Q) log N) where N is the number of intervals and Q is the number of queries. Sorting and heap operations dominate the complexity. Space Complexity: O(N + Q) for storing intervals, queries, and the heap.

Solution

The solution uses a two-step approach:

  1. Sort the queries while keeping track of their original indices.
  2. Sort intervals by their starting values. For each query (in increasing order), add intervals that start before or at this query to a min-heap, where each entry is the size of the interval along with its end value. Then, remove intervals from the heap that do not cover the query (their end value is less than the query). The heap’s top element (if available) holds the smallest interval size that contains the query.
  3. Place the answer in a result array at the position corresponding to the original query order.

Data structures used: Sorting arrays and a min-heap for efficient retrieval and removal.

Code Solutions

import heapq

def minInterval(intervals, queries):
    # Sort intervals by their starting point.
    intervals.sort(key=lambda itv: itv[0])
    
    # Prepare queries sorted by their value, keeping track of original index.
    sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])
    
    result = [-1] * len(queries)
    min_heap = []
    i = 0  # for intervals

    # Process each query in ascending order.
    for q, qi in sorted_queries:
        # Add all intervals that start <= current query.
        while i < len(intervals) and intervals[i][0] <= q:
            start, end = intervals[i]
            # Compute the size of the interval.
            size = end - start + 1
            # Push tuple: (size, end) into the min-heap.
            heapq.heappush(min_heap, (size, end))
            i += 1
        # Remove intervals that do not cover the current query.
        while min_heap and min_heap[0][1] < q:
            heapq.heappop(min_heap)
        # The top of the heap (if any) is the smallest interval covering the query.
        if min_heap:
            result[qi] = min_heap[0][0]
    return result

# Example usage
intervals = [[1,4],[2,4],[3,6],[4,4]]
queries = [2,3,4,5]
print(minInterval(intervals, queries))  # Output: [3, 3, 1, 4]
← Back to All Questions