My Calendar I: Booking Without Double Booking

This one is a Medium-rated classic reported from Google, Amazon, Salesforce interviews: "My Calendar I". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Merge Intervals pattern on sight. Part 10 of 11 in the Merge Intervals arc.

The Problem

Implement MyCalendar with a single method book(start, end) over the half-open interval [start, end): return True and store the event if it does not double-book with any existing event, else False. A design-flavored interval question — state lives across calls.

book(10, 20) -> True
book(15, 25) -> False   (collides with [10, 20))
book(20, 30) -> True    (touching is fine: half-open)

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

The heart is the overlap predicate for half-open intervals: [a, b) and [c, d) collide exactly when a is less than d and c is less than b. Everything else — linear list, sorted list, tree — is a data structure choice layered on that one boolean expression.

The Approach

Baseline: keep a list of bookings and test the predicate against each — O(n) per booking, perfectly acceptable as a first answer. The upgrade interviewers want next: keep bookings sorted (Python's bisect on start times) so each booking checks only its two neighbors, O(log n) search plus O(n) insert.

The predicate deserves ten seconds of care: writing it as start < other_end and other_start < end handles every case without enumeration — memorize it as a unit.

Python Solution

import bisect


class MyCalendar:
    """Bookings over half-open intervals, no double booking."""

    def __init__(self) -> None:
        self.starts: list[int] = []
        self.ends: list[int] = []

    def book(self, start: int, end: int) -> bool:
        i = bisect.bisect_right(self.starts, start)
        # neighbor before must end by our start; neighbor after must start at or past our end
        if i > 0 and self.ends[i - 1] > start:
            return False
        if i < len(self.starts) and self.starts[i] < end:
            return False
        self.starts.insert(i, start)
        self.ends.insert(i, end)
        return True

Complexity

• Time: O(log n) search, O(n) insert per booking — bisect finds the slot; list insertion shifts elements
• Space: O(n) — stored bookings

Interview Tips and Follow-Ups

• The escalation path is the question: My Calendar II allows one overlap (track double-booked regions), III asks max concurrency (event sweep). Know the trilogy.
• A balanced BST or an interval tree makes insert O(log n) too — in Python, mention sortedcontainers.SortedList as the practical stand-in.
• Confirm half-open semantics before coding; closed intervals flip the touching case and both comparisons.

More Merge Intervals problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.