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>
C# 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
public List<Span> MergeSpans(List<Span> spans) {
}Worked examples
| Call | Result |
|---|---|
MergeSpans(new List<Span> { new Span(1, 3), new Span(2, 6), new Span(8, 10) }) | new List<Span> { new Span(1, 6), new Span(8, 10) } |
MergeSpans(new List<Span> { new Span(5, 6), new Span(1, 3) }) | new List<Span> { new Span(1, 3), new Span(5, 6) } |
MergeSpans(new List<Span> { new Span(1, 4), new Span(4, 5) }) | new List<Span> { new Span(1, 5) } |
MergeSpans(new List<Span> { new Span(1, 10), new Span(2, 3) }) | new List<Span> { new Span(1, 10) } |
Hint
Sort by start, then sweep: either the next one extends the current stretch, or it begins a new one.
Reference solution in C#
public List<Span> MergeSpans(List<Span> spans) {
var live = spans.Where(s => s.Finish > s.Start).OrderBy(s => s.Start).ToList();
var result = new List<Span>();
foreach (var s in live) {
if (result.Count > 0 && s.Start <= result[result.Count - 1].Finish) {
var last = result[result.Count - 1];
last.Finish = Math.Max(last.Finish, s.Finish);
} else {
result.Add(new Span(s.Start, s.Finish));
}
}
return result;
}