Practice: Fitting a New Booking Into a Day

A day's bookings are sorted and do not overlap: add one more and merge whatever it touches, in one pass and without sorting again.

Inserting one interval into a sorted list that has no overlaps uses the merge's overlap test in a single pass, with no sort. A workshop's bench is booked [1, 2], [4, 5], [6, 8], [9, 11] and [13, 14], sorted by start, with closed times that merge when they touch. A new booking, [7, 10], arrives. Return the day's bookings with the new one added and anything it overlaps merged, in O(n) time.

Show the answer and a solution

The day becomes [1, 2], [4, 5], [6, 11] and [13, 14]. The pass has three phases. Copy every booking that ends before the new one starts. Then, while a booking starts at or before the new one's end, they overlap: widen the new booking to the smaller start and the larger end. Then append the widened booking and copy the rest. Here [6, 8] and [9, 11] both overlap [7, 10] and widen it to [6, 11].

text

before
          1   3   5   7   9   11  13
[1, 2]    ====
[4, 5]          ====
[6, 8]              ======
[9, 11]                   ======
[13, 14]                          ====
new                   ========
after
          1   3   5   7   9   11  13
[1, 2]    ====
[4, 5]          ====
[6, 11]             ============
[13, 14]                          ====

The listing inserts [7, 10], then [3, 3], which overlaps nothing and lands between [1, 2] and [4, 5].

insert.pypy

def insert(bookings: list[list[int]], new: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    start, end = new
    i = 0
    while i < len(bookings) and bookings[i][1] < start:
        result.append(bookings[i])
        i += 1
    while i < len(bookings) and bookings[i][0] <= end:
        start = min(start, bookings[i][0])
        end = max(end, bookings[i][1])
        i += 1
    result.append([start, end])
    result.extend(bookings[i:])
    return result


bookings = [[1, 2], [4, 5], [6, 8], [9, 11], [13, 14]]
print("after inserting [7, 10]:", insert(bookings, [7, 10]))
print("after inserting [3, 3]: ", insert(bookings, [3, 3]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

after inserting [7, 10]: [[1, 2], [4, 5], [6, 11], [13, 14]]
after inserting [3, 3]:  [[1, 2], [3, 3], [4, 5], [6, 8], [9, 11], [13, 14]]

Each booking is read once, so the pass is O(n) time and O(n) space for the result. Appending [7, 10] and running the full merge also works, but sorts again for O(n log n), throwing away the order the list already had.

← → move through sections and cards