LeetCode 731: My Calendar II

Problem Restatement

We need to implement a calendar that supports event bookings.

Each booking is a half-open interval:

[start, end)

A booking is allowed if it does not create a triple booking.

This means:

• One event overlapping another is allowed.
• Three events overlapping at the same time is forbidden.

We must implement:

book(start, end)

Return:

• True if the event can be added.
• False if adding it would create a triple booking.

The official statement defines events as half-open intervals and allows double booking while rejecting any booking that causes three active events at the same time. (leetcode.com)

Input and Output

Example class shape:

class MyCalendarTwo:

    def __init__(self):
        ...

    def book(self, start: int, end: int) -> bool:
        ...

Examples

Example 1

calendar = MyCalendarTwo()

calendar.book(10, 20)  # True
calendar.book(50, 60)  # True
calendar.book(10, 40)  # True
calendar.book(5, 15)   # False
calendar.book(5, 10)   # True
calendar.book(25, 55)  # True

Let us examine the important steps.

After:

book(10, 20)
book(10, 40)

the interval:

[10, 20)

is double booked.

Now consider:

book(5, 15)

This overlaps with both previous events during:

[10, 15)

That would create a triple booking, so the answer is:

False

The booking is rejected and is not stored.

First Thought: Check All Overlaps

For My Calendar I, we rejected any overlap.

Now overlaps are allowed, but only up to two simultaneous events.

A direct idea is:

1. Store all booked intervals.
2. When adding a new interval, check how many overlaps it creates.

The important observation is that triple booking happens exactly when the new interval overlaps a region that is already double booked.

So instead of tracking counts everywhere, we can explicitly store all double-booked intervals.

Key Insight

We maintain two lists:

booked

stores all accepted bookings.

overlaps

stores all intervals that are already double booked.

When adding a new booking:

1. First check whether it overlaps any interval in overlaps.

   • If yes, triple booking would happen.
   • Reject immediately.

2. Otherwise, compare the new interval with all existing bookings.

   • Every overlap creates a new double-booked interval.
   • Add those overlap regions to overlaps.

3. Finally, add the new booking to booked.

The crucial idea is:

triple booking occurs exactly when the new interval
intersects an already double-booked interval

Algorithm

Maintain:

self.booked
self.overlaps

For book(start, end):

Step 1: Check Triple Booking

Loop over all intervals in self.overlaps.

If the new interval overlaps any of them, return False.

Step 2: Create New Double Bookings

Loop over all intervals in self.booked.

Whenever the new interval overlaps an existing booking:

1. Compute the intersection.
2. Add that intersection to self.overlaps.

Step 3: Store the Booking

Append the new interval to self.booked.

Return True.

Correctness

The list booked contains every accepted booking.

The list overlaps contains every interval where exactly two accepted bookings overlap.

Before accepting a new booking, the algorithm checks whether it overlaps any interval in overlaps. If it does, then there already exist two events active during that overlap interval. Adding the new booking would create a time region where three events are simultaneously active. Therefore returning False is correct.

If the new booking does not overlap any interval in overlaps, then no triple booking can occur. The algorithm then compares the new booking against all existing bookings. Every intersection between the new booking and an existing booking creates a new region with exactly two simultaneous events. Adding those intersections to overlaps correctly updates the double-booked regions.

Finally, the new booking is added to booked.

Since the algorithm rejects exactly the bookings that would intersect an already double-booked interval, it accepts exactly the bookings that preserve the invariant that no time point belongs to three events.

Complexity

Let n be the number of accepted bookings.

In the worst case, the overlap list can also grow linearly.

Implementation

class MyCalendarTwo:

    def __init__(self):
        self.booked = []
        self.overlaps = []

    def book(self, start: int, end: int) -> bool:

        for s, e in self.overlaps:
            if start < e and s < end:
                return False

        for s, e in self.booked:
            if start < e and s < end:
                overlap_start = max(start, s)
                overlap_end = min(end, e)

                self.overlaps.append(
                    (overlap_start, overlap_end)
                )

        self.booked.append((start, end))

        return True

Code Explanation

The constructor initializes two lists:

self.booked = []
self.overlaps = []

booked stores all accepted events.

overlaps stores all regions that already have two events.

The first loop checks for triple booking:

for s, e in self.overlaps:
    if start < e and s < end:
        return False

The overlap condition:

start < e and s < end

means the intervals share some non-empty time region.

If this happens against an already double-booked interval, triple booking would occur.

The second loop builds new double-booked regions:

for s, e in self.booked:

If the new event overlaps an old one, compute the intersection:

overlap_start = max(start, s)
overlap_end = min(end, e)

This intersection becomes newly double booked:

self.overlaps.append(
    (overlap_start, overlap_end)
)

Finally, store the accepted booking:

self.booked.append((start, end))

Testing

def run_tests():
    cal = MyCalendarTwo()

    assert cal.book(10, 20) is True
    assert cal.book(50, 60) is True
    assert cal.book(10, 40) is True
    assert cal.book(5, 15) is False
    assert cal.book(5, 10) is True
    assert cal.book(25, 55) is True

    cal = MyCalendarTwo()

    assert cal.book(1, 5) is True
    assert cal.book(2, 6) is True
    assert cal.book(6, 8) is True
    assert cal.book(3, 4) is False

    cal = MyCalendarTwo()

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

    print("all tests passed")

run_tests()