# LeetCode 729: My Calendar I

## Problem Restatement

We need to implement a calendar.

The calendar supports one operation:

```python
book(startTime, endTime)
```

Each booking represents a half-open interval:

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

| Item | Meaning |
|---|---|
| Constructor | `MyCalendar()` creates an empty calendar |
| Method | `book(startTime, endTime)` tries to add one event |
| Return value | `True` if the event is accepted, otherwise `False` |
| Interval type | Half-open interval `[startTime, endTime)` |
| Rejection rule | Reject only when there is a non-empty overlap |

Example class shape:

```python
class MyCalendar:

    def __init__(self):
        ...

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

## Examples

### Example 1

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

```text
[10, 20)
[15, 25)
```

These two intervals overlap from `15` to `20`.

The third booking is accepted because:

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

```text
[s, e)
```

and a new interval:

```text
[startTime, endTime)
```

they overlap if:

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

```python
[10, 20)
[20, 30)
```

Here:

```python
20 < 20
```

is false, so the intervals do not overlap.

## Algorithm

Keep a list called `bookings`.

Each item is a pair:

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

| Metric | Value | Why |
|---|---:|---|
| Time per `book` call | `O(n)` | We may compare with every existing booking |
| Space | `O(n)` | We store all accepted bookings |

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

## Implementation

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

```python
self.bookings = []
```

Every accepted event will be stored in this list.

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

```python
for start, end in self.bookings:
```

The overlap check is:

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

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

The booking is added only after all checks pass.

## Testing

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

| Test | Why |
|---|---|
| `book(10, 20)`, `book(15, 25)`, `book(20, 30)` | Standard example with overlap and endpoint touching |
| Adjacent intervals | Confirms half-open interval logic |
| New interval inside old interval | Must be rejected |
| New interval before all old intervals | Should be accepted |
| New interval after all old intervals | Should be accepted |