1851.Minimum_Interval_to_Include_Each_Query(Hard).md

1851. Minimum Interval to Include Each Query (Hard)

Date and Time: Sep 6, 2024, 19:26 (EST)

Link: https://leetcode.com/problems/minimum-interval-to-include-each-query/

Question:

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: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 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]

Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 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

Walk-through:

1. We first sort intervals and queries and use res{} to store the queries's corrsponding minimum interval length. Because we sort them already, we need to use hashmap to return the original order of queries later.

2. Loop over queries and use a variaible i to keep track of current interval we at, we only add intervals to the heap that is within the range of current query (if intervals[i][0] <= query). We store the interval into minHeap with (length, right of the interval).

3. After adding all current related intervals into minHeap, we need to check if there is any invalid interval that is too left for current query, then we pop all invalid intervals (if minHeap[0][1] < query). Next, we store the top of minHeap into res[query] if minHeap else -1.

4. We can use list comprehension to recover the original order of the queries with the minimum length of interval.

Python Solution:

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        res = {}
        minHeap = []
        i = 0
        for query in sorted(queries):
            while i < len(intervals) and intervals[i][0] <= query:
                heapq.heappush(minHeap, (intervals[i][1]-intervals[i][0]+1, intervals[i][1]))
                i += 1
            # Pop invalid intervals from minHeap
            while minHeap and minHeap[0][1] < query:
                heapq.heappop(minHeap)
            res[query] = minHeap[0][0] if minHeap else -1
        return [res[query] for query in queries]

Time Complexity: $O(nlog\ n + mlog\ m)$, n is the length of intervals, m is the length of queries. Because we sort both of them.
Space Complexity: $O(n)$, the worst case we store all the intervals into res{}.