729 - My Calendar I

Difficulty: Medium | Pattern: Sorted Container / Binary Search | Company tags: Google, Amazon, Facebook

Problem Statement

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events).

Implement the MyCalendar class with a book(start, end) method that returns true if the event can be added to the calendar, and false otherwise. The event spans the half-open interval [start, end).

Example:

MyCalendar cal = new MyCalendar();
cal.book(10, 20) → true
cal.book(15, 25) → false  (overlaps [10,20))
cal.book(20, 30) → true   (starts where first ends — no overlap)

Algorithm Flow

Approach 1: Sorted List + Binary Search — O(log n) per booking

Key insight: Two intervals [s1,e1) and [s2,e2) overlap if s1 < e2 and s2 < e1. Store events sorted by start. For a new event, only need to check its neighbors.

from sortedcontainers import SortedList

class MyCalendar:
    def __init__(self):
        self.calendar = SortedList()
    
    def book(self, start: int, end: int) -> bool:
        idx = self.calendar.bisect_left((start,))
        
        # Check next event (start of next >= start of new)
        if idx < len(self.calendar):
            ns, ne = self.calendar[idx]
            if start < ne and ns < end:  # overlap
                return False
        
        # Check previous event
        if idx > 0:
            ps, pe = self.calendar[idx - 1]
            if ps < end and start < pe:  # overlap
                return False
        
        self.calendar.add((start, end))
        return True

Approach 2: Simple List — O(n) per booking

class MyCalendar:
    def __init__(self):
        self.events = []
    
    def book(self, start: int, end: int) -> bool:
        for s, e in self.events:
            if start < e and s < end:
                return False
        self.events.append((start, end))
        return True

Dry Run

book(10,20) → no events, add → True book(15,25) → check (10,20): 15 lt 20 and 10 lt 25 → overlap → False book(20,30) → check (10,20): 20 lt 20? No → no overlap → add → True ✓

Complexity

Approach	Time per call	Space
SortedList	O(log n)	O(n)
Simple List	O(n)	O(n)