Heaps and intervals

Heaps: the k largest

A heap gives the smallest item in O(1) and adds or removes items in O(log n). Python's heapq module keeps a heap inside a plain list (a min-heap: the smallest first).

The k most frequent words, the k closest points, the kth largest number: keep a heap of the best k so far. For the k largest, use a min-heap of size k: its smallest item is the weakest of the current top k, and any new item bigger than it replaces it.

import heapq

def k_largest(nums, k):
    heap = []                            # the k largest so far; heap[0] is the smallest of them
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)   # drop the weakest, add x
    return sorted(heap, reverse=True)

print(k_largest([5, 1, 9, 3, 7, 2, 8], 3))
print(heapq.nlargest(3, [5, 1, 9, 3, 7, 2, 8]))

O(n log k), better than sorting everything (O(n log n)) when k is small. heapq.nlargest(k, items) does exactly this. For a max-heap, push negated values.

Heaps also merge k sorted lists (push the front of each list, pop the smallest, push its successor), and run Dijkstra's algorithm.

Intervals: sort first

Interval problems (merge overlapping meetings, insert an interval, can one person attend all meetings?) almost always start by sorting by start time. Then overlaps are only possible between neighbours.

Merge overlapping intervals. After sorting, each interval either overlaps the last merged one (its start ≤ that one's end: extend the end) or starts a new one:

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:            # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge([[8, 10], [1, 3], [2, 6], [15, 18], [9, 12]]))
print(merge([[1, 10], [2, 3]]))

Careful with the end: use max, because one interval can sit completely inside another ([1, 10] and [2, 3]).

Meeting rooms: sweep the events

How many rooms are needed for these meetings? Split every meeting into a start event (+1 room) and an end event (−1). Sort all the events by time, and sweep through them keeping a running count; the answer is the highest count. When a meeting ends exactly as another starts, process the end first, so the room can be reused. A min-heap of end times gives the same answer.

Mark lesson complete