Studio Booking Sheet
A small recording studio keeps one booking sheet for its single room. Each line is a block of hours, like [13, 15] for 1 pm to 3 pm. The sheet is always tidy: blocks are in time order and no two blocks overlap or touch, because touching blocks get written as one.
A band calls to add a new block. Sometimes it fits in a gap; sometimes it overlaps one or more existing blocks, which then become one longer session. You need to rewrite the sheet so it is tidy again.
Your task
Write addBooking(bookings, newBooking). bookings is a list of [start, end] blocks sorted by start, with no two blocks overlapping or touching. newBooking is one [start, end] block. Return the new sheet: all blocks including the new one, sorted by start, with every group of overlapping or touching blocks combined into one.
Blocks that share only an endpoint count as touching: [10, 12] and [12, 14] become [10, 14]. Every block has start ≤ end. Return a new list; the input sheet may be empty.
addBooking(bookings: int[][], newBooking: int[]) → int[][]
Examples
bookings = [[9, 10], [13, 15], [18, 20]] newBooking = [14, 19]
[[9, 10], [13, 20]]
[9, 10] ends before 14, so it stays as it is. [13, 15] overlaps the new block, and so does [18, 20]. All three together cover 13 to 20, so they become one session [13, 20].
bookings = [[9, 11], [16, 17]] newBooking = [12, 14]
[[9, 11], [12, 14], [16, 17]]
The new block fits in the gap between 11 and 16 without touching either neighbour, so it is simply slotted in between them.
Constraints
- 0 ≤ bookings.length ≤ 10,000
- 0 ≤ start ≤ end ≤ 1,000,000,000
- bookings is sorted, and for consecutive blocks a and b, a.end < b.start
Start with brute force
Append the new block to the list, then run a full merge: sort by start and sweep, combining overlapping blocks. It is correct and short.
But it costs O(n log n) for the sort and ignores that the sheet was already sorted and tidy. Only the new block is out of place, so one O(n) pass is enough.
Hints
0 of 4 shown- Hint 1
In the first example, sort the old blocks into three groups by how they relate to the new block [14, 19]. What are the groups?
- Hint 2
Every old block is either entirely before the new one (it ends before the new start), entirely after it (it starts after the new end), or it overlaps or touches it. Because the sheet is sorted, these three groups come in that order.
- Hint 3
The blocks in the middle group all merge with the new block into a single session. How do you get that session's start and end from them?
- Hint 4
Walk the sheet once. Copy blocks while
end < newStart. Then, whilestart ≤ newEnd, widen the new block:newStart = min(...),newEnd = max(...). Append the widened block. Copy everything that is left.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The sheet is already tidy, so only the new block can cause trouble, and it can only touch one run of neighbouring blocks. Split the sheet into before, overlapping and after, in one pass.
Trace the first example: sheet [9, 10], [13, 15], [18, 20], new block [14, 19].
[9, 10]: ends at 10 < 14. Before. Copy it.[13, 15]: ends at 15, not before 14, and starts at 13 ≤ 19. Overlaps. The new block widens to[min(14, 13), max(19, 15)] = [13, 19].[18, 20]: starts at 18 ≤ 19. Overlaps. Widen to[13, 20].- No blocks left. Append
[13, 20]. Result:[[9, 10], [13, 20]].
Mind the comparisons. A block is "before" only if it ends strictly before the new start; one ending exactly at the new start touches it and must merge. The same goes for ≤ in the second loop.
function addBooking(bookings, newBooking) {
let [start, end] = newBooking;
const result = [];
let i = 0;
// 1. Blocks that finish before the new one starts.
while (i < bookings.length && bookings[i][1] < start) {
result.push([...bookings[i]]);
i++;
}
// 2. Blocks that overlap or touch: absorb them.
while (i < bookings.length && bookings[i][0] <= end) {
start = Math.min(start, bookings[i][0]);
end = Math.max(end, bookings[i][1]);
i++;
}
result.push([start, end]);
// 3. Blocks that start after it ends.
for (; i < bookings.length; i++) result.push([...bookings[i]]);
return result;
}def add_booking(bookings, new_booking):
start, end = new_booking
result = []
i, n = 0, len(bookings)
# 1. Blocks that finish before the new one starts.
while i < n and bookings[i][1] < start:
result.append(list(bookings[i]))
i += 1
# 2. Blocks that overlap or touch: absorb them.
while i < n and bookings[i][0] <= end:
start = min(start, bookings[i][0])
end = max(end, bookings[i][1])
i += 1
result.append([start, end])
# 3. Blocks that start after it ends.
result.extend(list(b) for b in bookings[i:])
return resultRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.