My Calendar II

Problem Statement

Design a calendar class supporting book(start, end) that allows double booking but rejects any triple booking. Each call returns true if the event was added, false otherwise.

Input

Sequential calls to book(start, end). Events are half-open [start, end).

book(10, 20)
book(50, 60)
book(10, 40)
book(5, 15)
book(5, 10)
book(25, 55)

Output

Each call returns true (added) or false (rejected because the third concurrent booking would cause a triple).

true     # [10,20) — first event
true     # [50,60) — no conflict
true     # [10,40) — doubles [10,20)
false    # [5,15)  — would triple [10,15)
true     # [5,10)  — touches but doesn't overlap
true     # [25,55) — doubles [50,55), still no triple

Constraints

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

Intuition

Maintain two lists:

• bookings — every accepted event.
• overlaps — the regions where exactly two events already overlap.

For each new event:

1. If it intersects any region in overlaps → that would be a third overlap → reject.
2. Otherwise, for every existing booking it overlaps, record the intersection region in overlaps.
3. Add the new event to bookings.

       bookings layer:   [══════════]       [══════════]
       overlaps layer:        [═════]
                              ↑ two events already share this region
       new event:         [═══════]
                              ↑ would land inside an overlap → REJECT

Solution

class MyCalendarTwo:
    def __init__(self):
        self.bookings = []
        self.overlaps = []  # double-booked regions
 
    def book(self, start: int, end: int) -> bool:
        # Check against triple booking
        for os, oe in self.overlaps:
            if start < oe and end > os:
                return False
 
        # Record new double-bookings
        for bs, be in self.bookings:
            if start < be and end > bs:
                self.overlaps.append((max(start, bs), min(end, be)))
 
        self.bookings.append((start, end))
        return True

class MyCalendarTwo {
    private bookings: [number, number][] = [];
    private overlaps: [number, number][] = [];
 
    book(start: number, end: number): boolean {
        for (const [os, oe] of this.overlaps) {
            if (start < oe && end > os) return false;
        }
 
        for (const [bs, be] of this.bookings) {
            if (start < be && end > bs) {
                this.overlaps.push([Math.max(start, bs), Math.min(end, be)]);
            }
        }
 
        this.bookings.push([start, end]);
        return true;
    }
}

Complexity

Edge Case Thinking