Module 10 · Intervals and Sweep-Line Events

096. Calendar Booking I

Bridge · Download this solution · All solutions and shared helpers

Problem

Implement Calendar.book(start,end) for nonempty half-open intervals. Return True and store the booking only when it overlaps no previously accepted booking; otherwise return False without changing the calendar. Shared endpoints are allowed.

Examples

Example 1

run_operations(Calendar, [("book",10,20),("book",15,25),("book",20,30)])
=> [True, False, True]

Rejection leaves the endpoint-adjacent third booking possible.

Example 2

run_operations(Calendar, [])
=> []

No bookings produce no decisions.

Example 3

run_operations(Calendar, [("book",1,2),("book",1,2)])
=> [True, False]

An exact duplicate overlaps the accepted interval.

Reveal the worked solution and reasoning

Why this mechanism works

Keep accepted intervals sorted and disjoint. At the insertion position, only the immediate predecessor and successor can overlap the new interval; all farther intervals lie beyond them. Binary search locates these neighbors, although insertion into a Python list still shifts elements.

State and boundaries

bookings is sorted by start and pairwise nonoverlapping. A rejected operation leaves it unchanged.

Protocol

Find the insertion index by start.
Reject if the predecessor ends after start.
Reject if the successor starts before end.
Insert only after both checks pass.
Return acceptance.

Visualization

accepted [10,20), [30,40)
new [20,30) fits between both
new [15,25) crosses predecessor -> reject

Python implementation

from bisect import bisect_left
from structures import run_operations

class Calendar:
    def __init__(self):
        self.bookings = []

    def book(self, start, end):
        i = bisect_left(self.bookings, (start, end))
        if i and self.bookings[i - 1][1] > start:
            return False
        if i < len(self.bookings) and self.bookings[i][0] < end:
            return False
        self.bookings.insert(i, (start, end))
        return True

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

run_operations(Calendar, [("book",10,20),("book",15,25),("book",20,30)])

L6 __init__: self.bookings = []
self=Calendar{'bookings':[]}

L9 book: i = bisect_left(self.bookings, (start, end))
self=Calendar{'bookings':[]}; start=10; end=20; i=0

L14 book: self.bookings.insert(i, (start, end))
self=Calendar{'bookings':[...]}; start=10; end=20; i=0

L9 book: i = bisect_left(self.bookings, (start, end))
self=Calendar{'bookings':[...]}; start=15; end=25; i=1

L9 book: i = bisect_left(self.bookings, (start, end))
self=Calendar{'bookings':[...]}; start=20; end=30; i=1

L14 book: self.bookings.insert(i, (start, end))
self=Calendar{'bookings':[..., ...]}; start=20; end=30; i=1

Result: [True, False, True]. Rejection leaves the endpoint-adjacent third booking possible.

run_operations(Calendar, [])

L6 __init__: self.bookings = []
self=Calendar{'bookings':[]}

Result: []. No bookings produce no decisions.

Why the solution is correct

The predecessor is the latest earlier-starting interval, so if it ends no later than start, every earlier interval is safe. The successor is the earliest later-starting interval, so if end does not exceed its start, all later intervals are safe. Insertion therefore preserves disjointness exactly when accepted.

Time and space

O(log n) neighbor search plus O(n) list insertion per accepted booking; O(n) stored intervals. This is not an O(log n) update structure.

Common mistakes

Using >= for predecessor overlap rejects legitimate endpoint contact. Mutating before validation leaves rejected bookings in state.

Reasoning card

State: bookings is sorted by start and pairwise nonoverlapping. A rejected operation leaves it unchanged.

Invariant: Stored bookings remain pairwise non-overlapping.

Decision to rehearse: Check candidate against stored intervals or ordered neighbours.

Finish: Return acceptance

Transfer exercise

Replace the sorted list with a balanced ordered tree and separate lookup cost from insertion cost in the new bound.