Problems › JavaScript › dates
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>
Where you start
function mergeSpans(spans) {
}Worked examples
| Call | Result |
|---|---|
mergeSpans([{"start":1,"finish":3},{"start":2,"finish":6},{"start":8,"finish":10}]) | [{"start":1,"finish":6},{"start":8,"finish":10}] |
mergeSpans([{"start":5,"finish":6},{"start":1,"finish":3}]) | [{"start":1,"finish":3},{"start":5,"finish":6}] |
mergeSpans([{"start":1,"finish":4},{"start":4,"finish":5}]) | [{"start":1,"finish":5}] |
mergeSpans([{"start":1,"finish":10},{"start":2,"finish":3}]) | [{"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 JavaScript
function mergeSpans(spans) {
const live = spans.filter((s) => s.finish > s.start).sort((a, b) => a.start - b.start);
const result = [];
for (const s of live) {
const last = result[result.length - 1];
if (last && s.start <= last.finish) last.finish = Math.max(last.finish, s.finish);
else result.push({ start: s.start, finish: s.finish });
}
return result;
}