LeetCode 729: My Calendar I

Problem Restatement

We need to implement a calendar.

The calendar supports one operation:

book(startTime, endTime)

Each booking represents a half-open interval:

[startTime, endTime)

This means the event includes startTime, but does not include endTime.

A new event can be added only if it does not create a double booking. A double booking happens when the new event overlaps with an existing event. If the event can be added, return True. Otherwise, return False and do not add it. The official statement defines each event as a half-open interval and asks book to reject bookings that create a non-empty intersection.

Input and Output

Example class shape:

class MyCalendar:

    def __init__(self):
        ...

    def book(self, startTime: int, endTime: int) -> bool:
        ...

Examples

Example 1

calendar = MyCalendar()

calendar.book(10, 20)  # True
calendar.book(15, 25)  # False
calendar.book(20, 30)  # True

The first booking is accepted because the calendar is empty.

The second booking is rejected because:

[10, 20)
[15, 25)

These two intervals overlap from 15 to 20.

The third booking is accepted because:

[10, 20)
[20, 30)

These two intervals touch at 20, but they do not overlap. The first interval excludes 20, so the intersection is empty.

First Thought: Store All Bookings

The simplest approach is to store every accepted booking in a list.

When a new booking arrives, compare it with every existing booking.

If it overlaps with any existing booking, reject it.

If it overlaps with none of them, append it to the list and accept it.

This is enough for the problem constraints and is easy to reason about.

Key Insight

Two half-open intervals overlap exactly when both intervals start before the other one ends.

For an existing interval:

[s, e)

and a new interval:

[startTime, endTime)

they overlap if:

startTime < e and s < endTime

This condition handles all cases correctly.

If one interval ends exactly when the other starts, there is no overlap.

For example:

[10, 20)
[20, 30)

Here:

20 < 20

is false, so the intervals do not overlap.

Algorithm

Keep a list called bookings.

Each item is a pair:

(start, end)

When book(startTime, endTime) is called:

1. Loop over every existing booking (s, e).
2. Check whether the new interval overlaps with (s, e).
3. If it overlaps, return False.
4. If no overlap is found, append (startTime, endTime).
5. Return True.

Correctness

The calendar stores exactly the bookings that have already been accepted.

When a new booking is requested, the algorithm compares it with every accepted booking. If it overlaps with any one of them, adding it would create a double booking, so returning False is correct.

If the algorithm finishes the loop without finding an overlap, then the new interval has empty intersection with every accepted booking. Adding it cannot create a double booking. Therefore appending the interval and returning True is correct.

The overlap test is correct for half-open intervals. Two intervals [a, b) and [c, d) have a non-empty intersection exactly when a < d and c < b. This excludes cases like [10, 20) and [20, 30), which only touch at an endpoint but share no included time.

Therefore every accepted booking preserves the calendar invariant that no two stored events overlap.

Complexity

Let n be the number of accepted bookings already stored.

Across many calls, this simple version can take quadratic total time in the number of calls, because later calls scan more stored intervals.

Implementation

class MyCalendar:

    def __init__(self):
        self.bookings = []

    def book(self, startTime: int, endTime: int) -> bool:
        for start, end in self.bookings:
            if startTime < end and start < endTime:
                return False

        self.bookings.append((startTime, endTime))
        return True

Code Explanation

The constructor starts with an empty list:

self.bookings = []

Every accepted event will be stored in this list.

The book method checks the new interval against all previous intervals:

for start, end in self.bookings:

The overlap check is:

if startTime < end and start < endTime:
    return False

If this condition is true, the new event shares some time with an existing event, so we reject it immediately.

If the loop finishes, the event does not overlap with anything already stored:

self.bookings.append((startTime, endTime))
return True

The booking is added only after all checks pass.

Testing

def run_tests():
    cal = MyCalendar()

    assert cal.book(10, 20) is True
    assert cal.book(15, 25) is False
    assert cal.book(20, 30) is True

    cal = MyCalendar()
    assert cal.book(5, 10) is True
    assert cal.book(10, 15) is True
    assert cal.book(0, 5) is True
    assert cal.book(4, 6) is False

    cal = MyCalendar()
    assert cal.book(1, 100) is True
    assert cal.book(100, 200) is True
    assert cal.book(50, 60) is False
    assert cal.book(0, 1) is True

    print("all tests passed")

run_tests()