minimum_interval_to_include_each_query
1from heapq import heappush, heappop 2 3 4# @leet start 5class Solution: 6 def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]: 7 """ 8 This question asks us to find the smallest interval that contains a 9 set of queries, passed in as an array. 10 11 The brute force way of solving this problem involves an $O(n * q)$ solution, 12 where for each query, you iterate through the intervals array and calculate 13 the smallest interval that contains each query. 14 15 We can do better by sorting both the intervals and queries, reducing 16 runtime to $O(n log n + q log q)$, by using $O(n)$ space for a heap 17 to contain intervals, and $O(q)$ space to cache all queries. 18 19 We need the query cache because there can be duplicates as we iterate 20 through the sorted queries. 21 22 We iterate through the sorted queries and while we still have 23 intervals left, and our current query fits inside the current interval, 24 we add the interval to the heap. Next, while we've passed any intervals 25 that can no longer contain our query, we pop those out of the heap. 26 27 At the end, the top item of the heap contains the shortest interval. 28 If there is none, we set our cache for q to -1. 29 30 At the end, we return res[q] for each query. 31 """ 32 intervals.sort() 33 h, res, i = [], {}, 0 34 for q in sorted(queries): 35 while i < len(intervals) and intervals[i][0] < q: 36 l, r = intervals[i] 37 heappush(h, (r - l + 1, r)) 38 i += 1 39 40 while h and h[0][1] < q: 41 heappop(h) 42 res[q] = h[0][0] if h else -1 43 return [res[q] for q in queries] 44 45 46# @leet end 47 48 49def test(): 50 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]: 8 """ 9 This question asks us to find the smallest interval that contains a 10 set of queries, passed in as an array. 11 12 The brute force way of solving this problem involves an $O(n * q)$ solution, 13 where for each query, you iterate through the intervals array and calculate 14 the smallest interval that contains each query. 15 16 We can do better by sorting both the intervals and queries, reducing 17 runtime to $O(n log n + q log q)$, by using $O(n)$ space for a heap 18 to contain intervals, and $O(q)$ space to cache all queries. 19 20 We need the query cache because there can be duplicates as we iterate 21 through the sorted queries. 22 23 We iterate through the sorted queries and while we still have 24 intervals left, and our current query fits inside the current interval, 25 we add the interval to the heap. Next, while we've passed any intervals 26 that can no longer contain our query, we pop those out of the heap. 27 28 At the end, the top item of the heap contains the shortest interval. 29 If there is none, we set our cache for q to -1. 30 31 At the end, we return res[q] for each query. 32 """ 33 intervals.sort() 34 h, res, i = [], {}, 0 35 for q in sorted(queries): 36 while i < len(intervals) and intervals[i][0] < q: 37 l, r = intervals[i] 38 heappush(h, (r - l + 1, r)) 39 i += 1 40 41 while h and h[0][1] < q: 42 heappop(h) 43 res[q] = h[0][0] if h else -1 44 return [res[q] for q in queries]
def
minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:
7 def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]: 8 """ 9 This question asks us to find the smallest interval that contains a 10 set of queries, passed in as an array. 11 12 The brute force way of solving this problem involves an $O(n * q)$ solution, 13 where for each query, you iterate through the intervals array and calculate 14 the smallest interval that contains each query. 15 16 We can do better by sorting both the intervals and queries, reducing 17 runtime to $O(n log n + q log q)$, by using $O(n)$ space for a heap 18 to contain intervals, and $O(q)$ space to cache all queries. 19 20 We need the query cache because there can be duplicates as we iterate 21 through the sorted queries. 22 23 We iterate through the sorted queries and while we still have 24 intervals left, and our current query fits inside the current interval, 25 we add the interval to the heap. Next, while we've passed any intervals 26 that can no longer contain our query, we pop those out of the heap. 27 28 At the end, the top item of the heap contains the shortest interval. 29 If there is none, we set our cache for q to -1. 30 31 At the end, we return res[q] for each query. 32 """ 33 intervals.sort() 34 h, res, i = [], {}, 0 35 for q in sorted(queries): 36 while i < len(intervals) and intervals[i][0] < q: 37 l, r = intervals[i] 38 heappush(h, (r - l + 1, r)) 39 i += 1 40 41 while h and h[0][1] < q: 42 heappop(h) 43 res[q] = h[0][0] if h else -1 44 return [res[q] for q in queries]
This question asks us to find the smallest interval that contains a set of queries, passed in as an array.
The brute force way of solving this problem involves an $O(n * q)$ solution, where for each query, you iterate through the intervals array and calculate the smallest interval that contains each query.
We can do better by sorting both the intervals and queries, reducing runtime to $O(n log n + q log q)$, by using $O(n)$ space for a heap to contain intervals, and $O(q)$ space to cache all queries.
We need the query cache because there can be duplicates as we iterate through the sorted queries.
We iterate through the sorted queries and while we still have intervals left, and our current query fits inside the current interval, we add the interval to the heap. Next, while we've passed any intervals that can no longer contain our query, we pop those out of the heap.
At the end, the top item of the heap contains the shortest interval. If there is none, we set our cache for q to -1.
At the end, we return res[q] for each query.
def
test():