# LeetCode 731: My Calendar II

## Problem Restatement

We need to implement a calendar that supports event bookings.

Each booking is a half-open interval:

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

```python
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](https://leetcode.com/problems/my-calendar-ii/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Constructor | `MyCalendarTwo()` creates an empty calendar |
| Method | `book(start, end)` tries to add an event |
| Return value | `True` if accepted, otherwise `False` |
| Allowed | Single and double bookings |
| Forbidden | Triple bookings |

Example class shape:

```python
class MyCalendarTwo:

    def __init__(self):
        ...

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

## Examples

### Example 1

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

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

the interval:

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

is double booked.

Now consider:

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

This overlaps with both previous events during:

```text
[10, 15)
```

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

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

```python
booked
```

stores all accepted bookings.

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

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

## Algorithm

Maintain:

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

| Metric | Value | Why |
|---|---:|---|
| Time per booking | `O(n)` | We scan both stored lists |
| Space | `O(n)` | We store bookings and overlap intervals |

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

## Implementation

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

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

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

The overlap condition:

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

```python
for s, e in self.booked:
```

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

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

This intersection becomes newly double booked:

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

Finally, store the accepted booking:

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

## Testing

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

| Test | Why |
|---|---|
| Official-style example | Basic double/triple booking behavior |
| Nested overlap | Triple booking inside a smaller interval |
| Endpoint touching | Half-open intervals should not overlap at endpoints |
| Triple booking inside existing double booking | Core rejection logic |