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.
mergeSpans(spans: list<Span>) → list<Span>
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func mergeSpans(spans []Span) []Span {
}Worked examples
| Call | Result |
|---|---|
mergeSpans([]Span{Span{Start: 1, Finish: 3}, Span{Start: 2, Finish: 6}, Span{Start: 8, Finish: 10}}) | []Span{Span{Start: 1, Finish: 6}, Span{Start: 8, Finish: 10}} |
mergeSpans([]Span{Span{Start: 5, Finish: 6}, Span{Start: 1, Finish: 3}}) | []Span{Span{Start: 1, Finish: 3}, Span{Start: 5, Finish: 6}} |
mergeSpans([]Span{Span{Start: 1, Finish: 4}, Span{Start: 4, Finish: 5}}) | []Span{Span{Start: 1, Finish: 5}} |
mergeSpans([]Span{Span{Start: 1, Finish: 10}, Span{Start: 2, Finish: 3}}) | []Span{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 Go
func mergeSpans(spans []Span) []Span {
live := []Span{}
for _, s := range spans {
if s.Finish > s.Start {
live = append(live, s)
}
}
sort.Slice(live, func(i, j int) bool { return live[i].Start < live[j].Start })
result := []Span{}
for _, s := range live {
if n := len(result); n > 0 && s.Start <= result[n-1].Finish {
if s.Finish > result[n-1].Finish {
result[n-1].Finish = s.Finish
}
} else {
result = append(result, Span{Start: s.Start, Finish: s.Finish})
}
}
return result
}