LeetCode 732: My Calendar III

Problem Restatement

We need to implement a calendar.

Each event is a half-open interval:

[start, end)

A new event can always be added.

After each booking, we must return the largest number of events that overlap at any time.

This value is called the maximum k-booking. A k-booking means there is some non-empty time interval where k events are active at the same time. The official problem defines each event as [start, end) and asks book to return the maximum k among all previous events after adding the new one.

Input and Output

Example class shape:

class MyCalendarThree:

    def __init__(self):
        ...

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

Examples

Example 1

calendar = MyCalendarThree()

calendar.book(10, 20)  # 1
calendar.book(50, 60)  # 1
calendar.book(10, 40)  # 2
calendar.book(5, 15)   # 3
calendar.book(5, 10)   # 3
calendar.book(25, 55)  # 3

After the first booking, only one event exists, so the answer is 1.

After:

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

both events overlap on:

[10, 20)

So the maximum booking is 2.

After:

book(5, 15)

three events overlap on:

[10, 15)

So the maximum booking becomes 3.

Later bookings do not create a time with four overlapping events, so the answer stays 3.

First Thought: Count Active Events Over Time

The calendar range can be large:

0 <= start < end <= 10^9

So we cannot create an array for every time point.

But we do not need every time point.

The number of active events only changes at event boundaries:

• At start, one event becomes active.
• At end, one event stops being active.

So we can store only these changes.

Key Insight

Use a sweep line difference map.

For each booking [start, end):

delta[start] += 1
delta[end] -= 1

Then scan times in sorted order.

Keep a running count:

active += delta[time]

The largest value of active during the scan is the maximum number of overlapping events.

This works because every event contributes +1 starting at start and stops contributing at end.

The half-open interval matters. Since the event ends at end, we subtract at exactly end, not at end + 1.

Algorithm

Maintain a map:

time -> change in active event count

When book(start, end) is called:

1. Add 1 at start.
2. Add -1 at end.
3. Scan all time points in sorted order.
4. Accumulate the active event count.
5. Return the maximum active count seen during the scan.

In Python, a plain dictionary does not keep keys sorted by value for scanning. Because there are at most 400 calls, we can sort the keys on every call.

Correctness

For every booked interval [start, end), the algorithm adds +1 at start and -1 at end. Therefore, when we scan all boundary times in increasing order, the running value active equals the number of events active immediately after applying all changes at that boundary.

Between two consecutive boundary times, no event starts or ends. So the number of active events is constant on that whole region.

Therefore, the maximum overlap over all real time points must occur on some region after a boundary update. The scan checks exactly these regions by maintaining the running active count.

After each book call, the new event has been added to the difference map before the scan. Thus the returned maximum is computed over all events booked so far.

Complexity

Let n be the number of calls to book.

Since the problem allows at most 400 calls, this solution is simple and efficient enough.

Implementation

from collections import defaultdict

class MyCalendarThree:

    def __init__(self):
        self.delta = defaultdict(int)

    def book(self, start: int, end: int) -> int:
        self.delta[start] += 1
        self.delta[end] -= 1

        active = 0
        best = 0

        for time in sorted(self.delta):
            active += self.delta[time]
            best = max(best, active)

        return best

Code Explanation

The constructor creates the difference map:

self.delta = defaultdict(int)

For each new booking, we record where the active count changes:

self.delta[start] += 1
self.delta[end] -= 1

This represents one event becoming active at start and inactive at end.

Then we scan the boundary times in order:

for time in sorted(self.delta):

The running count is updated with the change at that time:

active += self.delta[time]

The answer is the largest active count seen:

best = max(best, active)

Finally, return best.

Testing

def run_tests():
    cal = MyCalendarThree()

    assert cal.book(10, 20) == 1
    assert cal.book(50, 60) == 1
    assert cal.book(10, 40) == 2
    assert cal.book(5, 15) == 3
    assert cal.book(5, 10) == 3
    assert cal.book(25, 55) == 3

    cal = MyCalendarThree()

    assert cal.book(1, 5) == 1
    assert cal.book(5, 10) == 1
    assert cal.book(2, 6) == 2
    assert cal.book(3, 7) == 3
    assert cal.book(8, 9) == 3

    cal = MyCalendarThree()

    assert cal.book(0, 100) == 1
    assert cal.book(10, 90) == 2
    assert cal.book(20, 80) == 3
    assert cal.book(30, 70) == 4

    print("all tests passed")

run_tests()