# LeetCode 732: My Calendar III

## Problem Restatement

We need to implement a calendar.

Each event is a half-open interval:

```text
[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

| Item | Meaning |
|---|---|
| Constructor | `MyCalendarThree()` creates an empty calendar |
| Method | `book(start, end)` adds an event |
| Return value | Maximum number of overlapping events after this booking |
| Interval type | Half-open interval `[start, end)` |
| Constraint | At most `400` calls to `book` |

Example class shape:

```python
class MyCalendarThree:

    def __init__(self):
        ...

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

## Examples

### Example 1

```python
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:

```python
book(10, 20)
book(10, 40)
```

both events overlap on:

```text
[10, 20)
```

So the maximum booking is `2`.

After:

```python
book(5, 15)
```

three events overlap on:

```text
[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:

```text
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)`:

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

Then scan times in sorted order.

Keep a running count:

```python
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:

```python
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`.

| Metric | Value | Why |
|---|---:|---|
| Time per booking | `O(n log n)` | Sort up to `2n` boundary times, then scan them |
| Space | `O(n)` | Store at most two boundary changes per booking |

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

## Implementation

```python
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:

```python
self.delta = defaultdict(int)
```

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

```python
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:

```python
for time in sorted(self.delta):
```

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

```python
active += self.delta[time]
```

The answer is the largest active count seen:

```python
best = max(best, active)
```

Finally, return `best`.

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Official-style sequence | Checks increasing overlap and stable maximum |
| Adjacent intervals | Confirms `[start, end)` endpoint behavior |
| Nested intervals | Maximum overlap increases each time |
| Later disjoint interval | Maximum can stay unchanged |