LC 1851 - Minimum Interval to Include Each Query

Question

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 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 <= 105
• 1 <= queries.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 107
• 1 <= queries[j] <= 107

Links

Question here and solution here

Solution

concept

The main concept here is to first sort both the intervals and queries. The idea here is to use a min heap to keep track the length of the intervals.

For each query, we will add in intervals (in sorted order) to our min heap in the format of: (length of the interval, right end point) The right end will help us determine if the interval is still valid for the current query.

For each query:

1. we only add in interval if left end <= query, this will at least qualify the interval for our current query
2. we then remove interval that right end < query because this interval is too far left, meaning the query is not in the interval and therefore this is not qualified.
3. finally we look at the top of the heap and get the answer, since what is left in the heap are all valid.

A few things to note:

1. by adding and removing before actually look at the top of the heap, intervals that both right and left end on the left will be removed before consideration.
2. since the queries and intervals are sorted, whenever we pop the invalid intervals, we are sure this interval also won’t be valid for future query.
3. we need to restore the order of queries for the actual answer.

code

class Solution:
	"""
	brute force
	TLE
	"""
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        interval_len = [r - l + 1 for l, r in intervals]
        ans = []
        for q in queries:
            tmp = float("inf")
            for i in range(len(intervals)):
                if intervals[i][0] <= q <= intervals[i][1]:
                    tmp = min(tmp, interval_len[i])
            ans.append(tmp if tmp != float("inf") else -1)
            
        return ans
        
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        idx, ans = 0, {}
        min_heap = [] # (length, right pointer)

        for q in sorted(queries): # just the copy of sorted queries
	        # add in all valid intervals for q
            while idx < len(intervals) and intervals[idx][0] <= q:
                l, r = intervals[idx]
                heapq.heappush(min_heap, (r - l + 1, r))
                idx += 1
            # remove all invalid intervals for q
            while min_heap and min_heap[0][1] < q:
                heapq.heappop(min_heap)
            
            ans[q] = min_heap[0][0] if min_heap else -1

        return [ans[q] for q in queries]

Complexity

time: $O(n \log n + m \log m)$
space: $O(n + m)$
where m is the length of queries and m is the length of intervals.