Sweeping through time

Stop thinking about intervals. Think about the moments things start and stop, in order.

Key idea

The reframe

Questions about how many intervals are active at once are awkward to answer interval by interval, because the answer belongs to a moment rather than to any one interval.

So change what you iterate over. Each interval becomes two events: something begins, and later something ends. Sort all the events by time and walk them, keeping a running count that goes up on a start and down on an end.

The running count at any point is exactly how many intervals are active there, and every question about concurrency is a question about that count.

1def first_moment_reaching(intervals, threshold):2    """The first time at least this many intervals are active."""3    events = []4    for start, end in intervals:5        events.append((start, 1))6        events.append((end, -1))7    events.sort()                       # time, then -1 before +1 at equal times8 9    active = 010    for time, change in events:11        active += change12        if active >= threshold:13            return time14    return -115 16print(first_moment_reaching([[0, 30], [5, 10], [15, 20]], 2))17print(first_moment_reaching([[0, 30], [5, 10], [15, 20]], 3))

The two-list variant

The same sweep is often written without building an event list, by sorting starts and ends into two separate arrays and walking them with two indexes. Whichever time comes next decides whether the count rises or falls.

It avoids allocating pairs and reads well once you have seen it. The event-list version generalizes better, because an event can carry extra information such as which interval it belongs to.

The walk itself is the same whatever you are counting. Below it records, for each start, how many intervals had already finished by then.

1def finished_before_each_start(intervals):2    starts = sorted(pair[0] for pair in intervals)3    ends = sorted(pair[1] for pair in intervals)4 5    counts = []6    end_index = 07    for start in starts:8        while end_index < len(ends) and ends[end_index] <= start:9            end_index += 1              # this one was already over10        counts.append(end_index)11    return counts12 13print(finished_before_each_start([[0, 30], [5, 10], [15, 20]]))

One interval problem is still missing

There is a sixth problem in this family that asks, for each of many queries, the size of the smallest interval covering it. It needs a structure that can hand you the smallest thing currently available, which is a heap, so it waits until Unit 9.

The sweep you just learned is half of that solution. When you meet it there, the other half will be the only new part.

Code lab· 25 min

Sweep drills

build_events turns intervals into a sorted event list of (time, change) pairs with ends before starts at equal times. time_with_at_least returns the total time during which at least k intervals are active. count_overlapping_pairs returns how many pairs of intervals overlap at all.

solution.py

Tests

data = [[0, 30], [5, 10], [15, 20]]print(build_events([[1, 3], [3, 5]]))print(time_with_at_least(data, 1), time_with_at_least(data, 2), time_with_at_least(data, 3))print(count_overlapping_pairs(data), count_overlapping_pairs([]), count_overlapping_pairs([[1, 2], [1, 2], [1, 2]]))print(count_overlapping_pairs([[1, 3], [3, 5]]))

Output

Run tests to see output.

Problem· 25 min

Meeting Rooms Ii

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.

1def first_moment_reaching(intervals, threshold):2 """The first time at least this many intervals are active."""3 events = []4 for start, end in intervals:5 events.append((start, 1))6 events.append((end, -1))7 events.sort() # time, then -1 before +1 at equal times8 9 active = 010 for time, change in events:11 active += change12 if active >= threshold:13 return time14 return -115 16print(first_moment_reaching([[0, 30], [5, 10], [15, 20]], 2))17print(first_moment_reaching([[0, 30], [5, 10], [15, 20]], 3))