Merge overlapping bookings
A room calendar shows one bar per stretch of occupied time, so bookings that overlap or run straight into each other have to be folded together first.
- Bookings arrive in no particular order.
- Two bookings merge when they overlap, and also when one ends exactly where the next begins.
- A booking whose end is not after its start is empty and is dropped.
- The result comes back sorted by start time.
merge_spans(spans: list<Span>) → list<Span>
Where you start
def merge_spans(spans: list[Span]) -> list[Span]:
Worked examples
| Call | Result |
|---|---|
merge_spans([Span(start=1, finish=3), Span(start=2, finish=6), Span(start=8, finish=10)]) | [Span(start=1, finish=6), Span(start=8, finish=10)] |
merge_spans([Span(start=5, finish=6), Span(start=1, finish=3)]) | [Span(start=1, finish=3), Span(start=5, finish=6)] |
merge_spans([Span(start=1, finish=4), Span(start=4, finish=5)]) | [Span(start=1, finish=5)] |
merge_spans([Span(start=1, finish=10), Span(start=2, finish=3)]) | [Span(start=1, finish=10)] |
Hint
Sort by start, then sweep: either the next one extends the current stretch, or it begins a new one.
Reference solution in Python
def merge_spans(spans: list[Span]) -> list[Span]:
live = sorted((s for s in spans if s.finish > s.start), key=lambda s: s.start)
result = []
for s in live:
if result and s.start <= result[-1].finish:
result[-1].finish = max(result[-1].finish, s.finish)
else:
result.append(Span(start=s.start, finish=s.finish))
return result