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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Interval to Include Each Query

Difficulty: Hard

Problem Description

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i-th 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 j-th 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.

Key Insights

  • Each interval can be represented by its size, which is determined by its left and right bounds.
  • The queries ask for the minimum size of an interval that contains a specific value.
  • A sorted data structure can help efficiently find the smallest interval containing any query.
  • A combination of sorting, binary search, and a priority queue can be used to solve the problem efficiently.

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. Space Complexity: O(N + Q) for storing the intervals and results.

Solution

To solve the problem, we can follow these steps:

  1. Sort Intervals: Begin by sorting the intervals based on their left bounds. This allows us to efficiently find which intervals can potentially contain any queried value.
  2. Prepare for Queries: Create a list of queries along with their original indices to return results in the correct order after processing.
  3. Use a Min-Heap: Use a min-heap (priority queue) to keep track of the intervals that can contain the current query. The heap will store intervals sorted by size.
  4. Binary Search: For each query, use binary search to find all intervals that start before or at the query value.
  5. Update Results: For each interval that contains the query, add it to the heap, and check for the smallest interval size. If no intervals are found, the answer is -1.

Code Solutions

def minInterval(intervals, queries):
    from sortedcontainers import SortedList
    import heapq

    # Step 1: Sort intervals by left bound
    intervals.sort()
    # Step 2: Prepare queries with original indices
    queries_with_indices = sorted((q, i) for i, q in enumerate(queries))
    results = [-1] * len(queries)
    min_heap = []
    i = 0

    # Step 3: Process each query
    for query, index in queries_with_indices:
        # Step 4: Add intervals to the min-heap that can contain the query
        while i < len(intervals) and intervals[i][0] <= query:
            left, right = intervals[i]
            # Calculate size and push to min-heap
            size = right - left + 1
            heapq.heappush(min_heap, (size, right))
            i += 1
        
        # Step 5: Remove intervals from the heap that cannot contain the query
        while min_heap and min_heap[0][1] < query:
            heapq.heappop(min_heap)

        # Get the smallest interval size if available
        if min_heap:
            results[index] = min_heap[0][0]

    return results
← Back to All Questions