My Calendar I (LeetCode 729)

The problem

Design a calendar class with one method, book(start, end). Each event is the half-open interval [start, end): it includes start but not end. Accept the booking and return True if it does not overlap any event already booked; otherwise reject it and return False.

cal = MyCalendar()
cal.book(10, 20) -> True
cal.book(15, 25) -> False   (overlaps [10, 20) on 15..19)
cal.book(20, 30) -> True    (starts exactly when [10, 20) ends)

How to think about it

Start with the overlap test, since everything depends on it. People often write four cases: new starts inside old, new ends inside old, new contains old, old contains new. That is easy to get wrong.

The key insight: test for “not overlapping” and negate it. Two intervals do not overlap when one ends before the other starts: e <= bs or be <= s. Negate that and you get the full overlap test in two comparisons: s < be and bs < e. It covers all four cases at once.

Store bookings and check each new one. Keep a list of accepted bookings. For a new request, compare it with each. If any clash, reject; otherwise append. That is O(n) per call and O(n²) for n calls, which is fine for LeetCode’s limit of 1000 calls.

Which pattern is this? Intervals, the overlap check at the heart of the lesson. The tell is “book only if no overlap”. For larger inputs, keep bookings sorted (a balanced BST or sortedcontainers.SortedList) and check only the neighbours, for O(log n) per booking.

Approach

1. Keep a list books of accepted (start, end) pairs.
2. For book(s, e), loop over books. If any (bs, be) has s < be and bs < e, return False.
3. Otherwise append (s, e) and return True.

Solution

class MyCalendar:
    def __init__(self):
        self.books = []
    def book(self, s, e):
        for bs, be in self.books:
            if s < be and bs < e:              # neither ends before the other starts
                return False
        self.books.append((s, e)); return True
# cal = MyCalendar()
# [cal.book(10,20), cal.book(15,25), cal.book(20,30)] -> [True, False, True]

Dry run

Complexity

• Time: O(n) per booking, O(n²) for n bookings. Each call scans every accepted booking.
• Space: O(n). One entry per accepted booking.

Edge cases and pitfalls

• Back-to-back events are fine because the intervals are half-open: [10, 20) and [20, 30) share no time. Using <= in the test would wrongly reject them.
• A new event that contains an old one ([5, 40) against [10, 20)) is caught by the same two comparisons, with no extra case.
• Rejected bookings must not be stored. Append only after the loop finds no clash.
• Sorting the whole list on every call to then check neighbours costs O(n log n) per call, worse than the plain scan. Use a structure that stays sorted.

Related problems

• Meeting Rooms (LeetCode 252): the same overlap question, asked once for a whole list.
• Insert Interval (LeetCode 57): inserting into a sorted list, merging instead of rejecting.
• Snapshot Array (LeetCode 1146): another design problem where the right data structure makes each call cheap.