My Calendar I — Sorted Map, Balanced BST & Segment Tree Booking System Explained

Problem Statement#

LeetCode 729 — My Calendar I | Difficulty: Medium

Implement a MyCalendar class that stores events without double-booking.

A double booking happens when two events share any common point in time. An event is represented as a half-open interval [start, end).

Implement book(start, end) that returns true if the event can be added, false otherwise.

Constraints:

• 0 is less than or equal to start, which is less than end, which is less than or equal to 10^9
• At most 1000 calls to book

Example 1:

Input:  ["MyCalendar", "book", "book", "book"]
        [[], [10, 20], [15, 25], [20, 30]]
Output: [null, true, false, true]
Explanation:
  book(10, 20) -> true,  calendar: [10,20)
  book(15, 25) -> false, overlaps with [10,20)
  book(20, 30) -> true,  starts where previous ended (half-open: no conflict)

Why This Problem Matters#

My Calendar I is the cleanest interview question for interval-overlap detection with sorted data structures. Google, Uber, Amazon, and Doordash all rotate it because real systems — meeting scheduling, machine reservation, ad-slot booking, calendar widgets, network bandwidth allocation — solve exactly this problem at scale.

The naive O(n) check per booking is acceptable for n at 1000, but the interviewer always pushes for O(log n). Reaching that bound forces you to choose between three production-grade tools: a sorted map / TreeMap, a balanced BST, or a dynamic segment tree. Knowing which to reach for and why is the senior-level signal.

The Core Insight#

Two half-open intervals [s1, e1) and [s2, e2) overlap if and only if s1 is less than e2 and s2 is less than e1. Equivalently, they do not overlap when one ends at or before the other begins.

The naive check compares the new booking against every stored interval — O(n) per call. To beat that, you need a data structure that lets you find the two relevant neighbors in O(log n):

1. The latest event whose start is less than or equal to start
2. The earliest event whose start is greater than start

If neither neighbor overlaps the new booking, you can insert it. Two intervals can never overlap unless they are adjacent in start-order, so checking just these two neighbors is sufficient.

Why a sorted map / TreeMap works perfectly here:

• floorKey(start) — returns the largest key less than or equal to start, the predecessor event.
• ceilingKey(start) — returns the smallest key greater than or equal to start, the successor event.
• Insertion in O(log n).

In Python, SortedDict from sortedcontainers exposes bisect_left and bisect_right for the same effect. In Java, TreeMap has floorKey and ceilingKey natively. In JavaScript, you simulate with a sorted array plus binary search, or use a self-balancing BST library.

Visual Dry Run#

Trace book(10, 20), book(15, 25), book(20, 30) against an initially empty sorted map.

Step 1: book(10, 20)
  no events yet -> insert {10: 20}
  return true
  state: {10:20}
 
Step 2: book(15, 25)
  predecessor = floorKey(15) = 10, end = 20
  check: prev.end > 15 -> 20 > 15  YES, overlap detected
  return false
  state: {10:20}
 
Step 3: book(20, 30)
  predecessor = floorKey(20) = 10, end = 20
  check: prev.end > 20 -> 20 > 20  NO, no overlap (half-open)
  successor = ceilingKey(20) = none
  insert {20:30}
  return true
  state: {10:20, 20:30}

The "less than versus less than or equal to" boundary handling is the entire reason this problem feels tricky on a whiteboard.

Solution (Optimal)#

Python — SortedDict (sortedcontainers)#

from sortedcontainers import SortedDict
 
class MyCalendar:
    def __init__(self):
        self.cal = SortedDict()                        # maps start -> end, kept sorted
 
    def book(self, start: int, end: int) -> bool:
        # find index where 'start' would be inserted to keep sorted order
        idx = self.cal.bisect_right(start)             # smallest key strictly greater than start
 
        # check successor: its start must be at or after 'end'
        if idx < len(self.cal):
            next_start = self.cal.keys()[idx]          # earliest key greater than start
            if next_start < end:                       # successor starts before our end -> overlap
                return False
 
        # check predecessor: its end must be at or before 'start'
        if idx > 0:
            prev_start = self.cal.keys()[idx - 1]      # largest key at or below start
            if self.cal[prev_start] > start:           # predecessor extends past our start -> overlap
                return False
 
        # safe to insert
        self.cal[start] = end
        return True

Python — Naive O(n) Fallback#

class MyCalendar:
    def __init__(self):
        self.events = []                               # list of (start, end) tuples
 
    def book(self, start: int, end: int) -> bool:
        # check every existing interval for overlap
        for s, e in self.events:
            if start < e and s < end:                  # half-open overlap test
                return False
        self.events.append((start, end))
        return True

JavaScript — Sorted Array plus Binary Search#

class MyCalendar {
    constructor() {
        this.starts = [];                              // sorted array of start times
        this.ends = [];                                // ends[i] is end of starts[i]
    }
 
    // binary search: smallest index i with starts[i] >= target
    _lowerBound(target) {
        let lo = 0, hi = this.starts.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.starts[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
 
    book(start, end) {
        const idx = this._lowerBound(start);           // first event starting at or after start
 
        // successor check: its start must be >= our end
        if (idx < this.starts.length && this.starts[idx] < end) return false;
 
        // predecessor check: its end must be <= our start
        if (idx > 0 && this.ends[idx - 1] > start) return false;
 
        // insert in sorted position
        this.starts.splice(idx, 0, start);
        this.ends.splice(idx, 0, end);
        return true;
    }
}

Complexity: SortedDict / TreeMap solution: O(log n) per booking, O(n) space. Naive solution: O(n) per booking. Sorted-array JS version is O(log n) for search but O(n) for insertion due to splice — acceptable for n up to 1000.

Common Mistakes#

1. Using closed-interval logic on a half-open spec. The problem says half-open [start, end), so book(10, 20) followed by book(20, 30) should succeed. Using prev.end >= start instead of prev.end > start rejects valid bookings.
2. Checking only one neighbor. Some candidates only check the predecessor, missing successor overlap. You must verify both sides because the new event could be sandwiched between two existing ones.
3. Inserting before checking. If you insert first and then check, you accidentally compare the new event against itself.
4. Building a non-balanced BST manually. A naive BST degenerates to O(n) on monotonic inputs. Use the language's balanced map (TreeMap, SortedDict) or implement red-black or AVL — never plain BST.
5. Off-by-one in bisect. bisect_left gives the first index with key greater than or equal to start; bisect_right gives the first index with key strictly greater than start. The choice changes which neighbor counts as "predecessor".
6. Re-sorting on every insert. O(n log n) per call instead of O(log n). Maintain sorted order incrementally.

Interview Tips#

• State the half-open semantics first. Saying "I notice these are half-open intervals, so [10,20) and [20,30) should both succeed" earns credibility before you write code.
• Explain the two-neighbor argument. Many candidates check the entire list. Showing that only the immediate predecessor and successor matter is the key insight.
• Mention the data-structure ladder. "Sorted list O(n) -> sorted map O(log n) -> segment tree if we move to range counts." Demonstrating the ladder shows progression in your thinking.
• Ask about scale. "Will this be 10^3 or 10^7 bookings?" If it is small, the naive solution is fine and easier to verify. Senior engineers right-size the solution.
• Prepare the My Calendar II and III variants. They use the same scaffold with a count threshold — interviewers love asking the upgrade.

Follow-up Questions#

1. My Calendar II (LeetCode 731). Allow up to two simultaneous events; reject only on triple booking. Track double-booked intervals separately.
2. My Calendar III (LeetCode 732). Return the maximum k-booking after each insert. Use a difference array or sweep-line counter.
3. Persistent calendar with rollback. Use a persistent BST or a copy-on-write approach.
4. Distributed scheduling across shards. Partition by time bucket; each shard runs an independent sorted map.
5. Range queries: how many events overlap a given range. Move to a segment tree with lazy propagation.
6. Booking with priorities (allow override of low-priority events). Augment the BST node with priority and maintain a max-priority subtree pointer.

Key Takeaways#

• Two half-open intervals overlap when neither ends at or before the other begins; checking only the immediate predecessor and successor in start-order is sufficient.
• A sorted map (TreeMap, SortedDict, std::map) gives O(log n) insertion plus floor and ceiling lookup — the right tool for this class of problem.
• Half-open versus closed interval semantics change the comparison from greater-than to greater-than-or-equal — read the spec carefully.
• The naive O(n) solution is acceptable for n at 1000 but the interviewer almost always wants the O(log n) version.
• This template extends to My Calendar II, III, range coverage, and meeting-room style problems by augmenting the stored intervals with counts or boundaries.
• Mention the data-structure ladder (list, sorted map, segment tree) and pick the simplest one that meets the constraints — that is the engineering instinct interviewers reward.