My Calendar I

Problem Statement

Design a calendar class with a single method book(start, end). A new event can be added only if it doesn’t cause a double booking — i.e. doesn’t overlap any previously booked event. Events are half-open intervals [start, end).

Input

Sequential calls to book(start, end), each proposing a new event.

book(10, 20)
book(15, 25)
book(20, 30)

Output

Each book call returns true if the booking was added, false if rejected because it would overlap an existing one.

true     # [10,20) — first event, added
false    # [15,25) — overlaps [10,20), rejected
true     # [20,30) — touches [10,20) at 20 (half-open), added

Constraints

• 0 ≤ start < end ≤ 10⁹
• At most 1000 calls to book.

Intuition

For each new booking, scan the existing ones and test for overlap using the universal half-open formula:

   start < existing_end   AND   end > existing_start

If any existing booking overlaps → reject. Otherwise, store the booking and return true.

Solution

class MyCalendar:
    def __init__(self):
        self.bookings = []
 
    def book(self, start: int, end: int) -> bool:
        for s, e in self.bookings:
            if start < e and end > s:  # overlap check
                return False
        self.bookings.append((start, end))
        return True
 
# book() → O(n) per call.  Optimized: SortedList → O(log n)

class MyCalendar {
    private bookings: [number, number][] = [];
 
    book(start: number, end: number): boolean {
        for (const [s, e] of this.bookings) {
            if (start < e && end > s) return false;
        }
        this.bookings.push([start, end]);
        return true;
    }
}

Complexity

Edge Case Thinking