Walking the timeline once
Intervals & Sweep Line
The analogy
You have a pile of bookings and want to know the busiest moment. Rather than comparing every booking with every other, write down every start and every end as an event, sort them by time, then walk the timeline keeping a running count. One pass answers it.
Visualizer
Sweeping the timeline
step 1 / 14| timeline | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| bk 1 | █ | █ | █ | █ | |||||||||
| bk 2 | █ | █ | █ | █ | █ | ||||||||
| bk 3 | █ | █ | |||||||||||
| bk 4 | █ | █ | |||||||||||
| bk 5 | █ | █ | █ | ||||||||||
| concurrent |
Five bookings. What is the maximum number overlapping at once? Comparing every pair with every other is O(n²).5 bookings
def merge_intervals(iv):
iv.sort() # by start
out = []
for s, e in iv:
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
def max_concurrent(iv):
events = []
for s, e in iv:
events.append((s, +1))
events.append((e, -1))
# -1 before +1 at equal time => [start, end) semantics
events.sort(key=lambda x: (x[0], x[1]))
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
# O(n log n) — the sort dominatesCheck yourself
At an identical timestamp, why process end events before start events?