Minimum Interval to Include Each Query
- 3 min read
- LC-Hard
- Interval
3 years ago
Solution
- Draw out the problem first so that it's easier to visualize
- We will sort both the intervals (by start time) and queries, because we want to maximize our chances of finding the appropriate query
- This can be done if both intervals and queries are sorted because remember, the query value needs to reside in between the start time and the end time- and sorting the intervals by start time is a way to do this
- We will maintain a hashmap to store the value for each query since if we sort, we will lose the original order, and hence our output will be wrong
- For each interval we see, until the start time is past the current query time, we will add the intervals to a min heap, where the first value is the size of the interval (since we want to get the intervals with the smallest size for a query), and the second value is the end or right of the interval
- Why do we need the right interval?
- Because before we consider a possible interval from the min heap, we first need to check if the end time is before the query time, this means the interval finished before the current query, and we need to pop it out of the min heap before getting the minimum interval
- Before getting the top value from the min heap to assign to our query, we must remove invalid intervals first
- Invalid intervals are ones that end even before our current query begins
- These intervals obviously cannot be valid answers for the current query, so we pop them from the min heap until either the heap is empty or a valid interval is seen
| Time | Space | Explanation |
|---|---|---|
O(n log n + q log q) | O() | Main TC is from sorting both the intervals and the queries |
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
intervals.sort()
ans = {}
heap = [] # (size, heap)
i = 0
for query in sorted(queries):
# Add all valid intervals to min heap
while i < len(intervals) and intervals[i][0] <= query:
l, r = intervals[i]
heappush(heap, (r - l + 1, r))
i += 1
# Pop all invalid intervals, i.e. ones that end before the current query
while heap and heap[0][1] < query:
heappop(heap)
ans[query] = heap[0][0] if heap else -1
return [ans[query] for query in queries]