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>
Java 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
List<Span> mergeSpans(List<Span> spans) {
}Worked examples
| Call | Result |
|---|---|
mergeSpans(Main.<Span>ls(new Span(1, 3), new Span(2, 6), new Span(8, 10))) | Main.<Span>ls(new Span(1, 6), new Span(8, 10)) |
mergeSpans(Main.<Span>ls(new Span(5, 6), new Span(1, 3))) | Main.<Span>ls(new Span(1, 3), new Span(5, 6)) |
mergeSpans(Main.<Span>ls(new Span(1, 4), new Span(4, 5))) | Main.<Span>ls(new Span(1, 5)) |
mergeSpans(Main.<Span>ls(new Span(1, 10), new Span(2, 3))) | Main.<Span>ls(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 Java
List<Span> mergeSpans(List<Span> spans) {
List<Span> live = new ArrayList<>();
for (Span s : spans) if (s.finish > s.start) live.add(s);
live.sort((a, b) -> a.start - b.start);
List<Span> result = new ArrayList<>();
for (Span s : live) {
if (!result.isEmpty() && s.start <= result.get(result.size() - 1).finish) {
Span last = result.get(result.size() - 1);
last.finish = Math.max(last.finish, s.finish);
} else {
result.add(new Span(s.start, s.finish));
}
}
return result;
}