Heaps and Priority Queues
87 / 170Heaps and Priority QueuesLesson 7 of 8About 53 min
Deferred from Unit 6 on purpose. Sort the queries, sweep the intervals, and keep the live ones in a heap.
Sort the intervals by start. Walk the sorted queries, and for each one: add every interval that has started by now, discard from the top every interval that has already ended, then read the smallest remaining.
Below is what that looks like at a single query point, with the intervals added by hand instead of by a moving index.
import heapq intervals = [[1, 4], [2, 4], [3, 6], [4, 4]]point = 3 heap = [] # (size, end), smallest size on topfor start, end in intervals: if start <= point: # has begun by now heapq.heappush(heap, (end - start + 1, end)) print("started by now:", sorted(heap))while heap and heap[0][1] < point: heapq.heappop(heap) # already ended, and never comes backprint("smallest still covering:", heap[0][0])The queries have to be answered in the order they were asked, but nothing says they have to be computed in that order. Type the two lines it prints.
queries = [5, 2, 9, 3] order = sorted(range(len(queries)), key=lambda i: queries[i])print("visit the queries in this positional order:", order) answers = [None] * len(queries)for position in order: answers[position] = queries[position] * 10 # stand-in for real work print(answers)Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.