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
std::vector<Span> mergeSpans(std::vector<Span> spans) {
}Worked examples
| Call | Result |
|---|---|
mergeSpans(std::vector<Span>{Span{1, 3}, Span{2, 6}, Span{8, 10}}) | std::vector<Span>{Span{1, 6}, Span{8, 10}} |
mergeSpans(std::vector<Span>{Span{5, 6}, Span{1, 3}}) | std::vector<Span>{Span{1, 3}, Span{5, 6}} |
mergeSpans(std::vector<Span>{Span{1, 4}, Span{4, 5}}) | std::vector<Span>{Span{1, 5}} |
mergeSpans(std::vector<Span>{Span{1, 10}, Span{2, 3}}) | std::vector<Span>{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++
std::vector<Span> mergeSpans(std::vector<Span> spans) {
std::vector<Span> live;
for (const auto& s : spans) if (s.finish > s.start) live.push_back(s);
std::sort(live.begin(), live.end(), [](const Span& a, const Span& b) { return a.start < b.start; });
std::vector<Span> result;
for (const auto& s : live) {
if (!result.empty() && s.start <= result.back().finish) {
result.back().finish = std::max(result.back().finish, s.finish);
} else {
result.push_back(Span{s.start, s.finish});
}
}
return result;
}