Add a booking to a sorted list of separate blocks

Three phases in one pass: copy the blocks that end before the new one starts; absorb every block that starts at or before the new one's end by widening it; then copy the rest. O(n) time and O(n) space for the output, no sort needed because the input is already sorted.

Using the sorted input is the point; re-sorting would be O(n log n).

A binary search can find where phase two starts, but copying keeps it O(n) anyway.

Keep the same touching rule as the merge question.

def add_booking(blocks: list[list[int]],
                new: list[int]) -> list[list[int]]:
    out: list[list[int]] = []
    start, end = new
    i = 0
    while i < len(blocks) and blocks[i][1] < start:  # wholly before
        out.append(blocks[i])
        i += 1
    while i < len(blocks) and blocks[i][0] <= end:  # touches: absorb
        start, end = min(start, blocks[i][0]), max(end, blocks[i][1])
        i += 1
    out.append([start, end])
    return out + blocks[i:]

Common mistakes

• Re-sorting everything.
• Forgetting blocks fully inside the new booking.

Name the three phases before coding.

Follow-up questions

Think of your answer first, then open the hint.

1. How do you do it in place?

   Show hint

   Find the range of absorbed blocks with two binary searches, then replace that slice.

2. What about removing a time range?

   Show hint

   Same three phases, but blocks in the middle are trimmed or split.