Intervals: merge and overlap
Bookings, shifts, outages and promotions are all intervals: (start, end) pairs. Almost every interval problem starts the same way: sort by start. Then a single pass can compare each interval with the last one you kept.
- Two sorted intervals overlap when the next start is before the current end. Decide on purpose whether touching intervals, like 9-10 and 10-11, count as one; here they do.
- Merging keeps a list and either extends the last interval or starts a new one.
- Gaps are the spaces between merged intervals.
- Rooms needed is the most intervals open at once: turn each interval into a +1 event at its start and a -1 event at its end, sort the events, and track the running count. Process an end before a start at the same time if a room freed at 10:00 can be reused at 10:00.
- Intersecting two schedules walks both sorted lists with two pointers.
Times in this lesson are minutes or hours as plain numbers, which keeps the logic visible.
def merge(intervals):
out = []
for s, e in sorted(intervals):
if out and s <= out[-1][1]:
out[-1] = (out[-1][0], max(out[-1][1], e))
else:
out.append((s, e))
return out
merge([(13, 15), (9, 10), (10, 12), (14, 16)])
Out: [(9, 12), (13, 16)]. Sorted first, then each interval extends the last one or starts a new one.