# LeetCode 252: Meeting Rooms

## Problem Restatement

We are given a list of meeting time intervals.

Each interval contains:

```python
[start, end]
```

A person can attend all meetings only if none of the meetings overlap.

We need to return:

- `True` if all meetings can be attended
- `False` if at least two meetings overlap

Two meetings overlap when one meeting starts before another meeting finishes.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of meeting intervals |
| Output | Boolean |
| Interval | `[start, end]` |
| Goal | Determine whether all meetings are non-overlapping |

Example function shape:

```python
def canAttendMeetings(intervals: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```python
intervals = [[0, 30], [5, 10], [15, 20]]
```

The first meeting runs from `0` to `30`.

The second meeting starts at `5`.

Since:

$$
5 < 30
$$

the meetings overlap.

So the answer is:

```python
False
```

Example 2:

```python
intervals = [[7, 10], [2, 4]]
```

After sorting:

```python
[[2, 4], [7, 10]]
```

The second meeting starts after the first meeting ends.

So the answer is:

```python
True
```

Example 3:

```python
intervals = [[1, 5], [5, 8]]
```

These meetings do not overlap.

The first meeting ends exactly when the second meeting starts.

So the answer is:

```python
True
```

## First Thought: Compare Every Pair

The simplest approach is to compare every meeting against every other meeting.

For two intervals:

```python
[a_start, a_end]
[b_start, b_end]
```

they overlap when:

$$
a_{start} < b_{end} \land b_{start} < a_{end}
$$

So we could check all pairs.

```python
class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        n = len(intervals)

        for i in range(n):
            for j in range(i + 1, n):
                a_start, a_end = intervals[i]
                b_start, b_end = intervals[j]

                if a_start < b_end and b_start < a_end:
                    return False

        return True
```

This works, but it checks too many pairs.

## Problem With Brute Force

If there are `n` meetings, the brute force solution compares many interval pairs.

The time complexity becomes:

$$
O(n^2)
$$

We can do better using sorting.

## Key Insight

If intervals are sorted by start time, then we only need to compare neighboring meetings.

Why?

Suppose the meetings are sorted:

```python
[start1, end1]
[start2, end2]
[start3, end3]
```

If meeting `2` does not overlap with meeting `1`, and meeting `3` starts after meeting `2`, then meeting `3` also cannot overlap with meeting `1`.

So after sorting, checking adjacent intervals is enough.

The overlap condition becomes:

$$
current_{start} < previous_{end}
$$

If this condition is true, the meetings overlap.

## Algorithm

First, sort the intervals by start time.

```python
intervals.sort()
```

Then scan from left to right.

For every meeting:

1. Compare its start time with the previous meeting's end time.
2. If the current meeting starts before the previous one ends, return `False`.
3. Otherwise continue.

If we finish the scan without finding overlap, return `True`.

## Correctness

After sorting, meetings appear in chronological order of start time.

Suppose we are currently examining:

```python
previous = [prev_start, prev_end]
current = [curr_start, curr_end]
```

If:

$$
curr_{start} < prev_{end}
$$

then the current meeting begins before the previous meeting finishes. Therefore the meetings overlap, and attending all meetings is impossible.

If instead:

```python
curr_start >= prev_end
```

then the current meeting starts at or after the previous meeting ends, so these two meetings do not overlap.

Because the intervals are sorted, any earlier meeting ends no later than `prev_end`. Therefore checking only neighboring intervals is sufficient to detect every possible overlap.

If no neighboring pair overlaps, then no meetings overlap at all, so attending all meetings is possible.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates the runtime |
| Space | `O(1)` or `O(log n)` | Depends on sorting implementation |

The scan after sorting is linear.

## Implementation

```python
class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort()

        for i in range(1, len(intervals)):
            prev_end = intervals[i - 1][1]
            curr_start = intervals[i][0]

            if curr_start < prev_end:
                return False

        return True
```

## Code Explanation

We first sort the intervals:

```python
intervals.sort()
```

Python sorts lists lexicographically, so intervals are sorted by start time automatically.

Then we scan neighboring intervals:

```python
for i in range(1, len(intervals)):
```

For each pair:

```python
prev_end = intervals[i - 1][1]
curr_start = intervals[i][0]
```

we check whether the current meeting starts too early.

```python
if curr_start < prev_end:
    return False
```

If overlap exists, attending all meetings is impossible.

If the loop finishes, every interval is compatible with the next one.

So we return:

```python
True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canAttendMeetings([[0, 30], [5, 10], [15, 20]]) is False
    assert s.canAttendMeetings([[7, 10], [2, 4]]) is True
    assert s.canAttendMeetings([[1, 5], [5, 8]]) is True
    assert s.canAttendMeetings([]) is True
    assert s.canAttendMeetings([[1, 2]]) is True
    assert s.canAttendMeetings([[1, 4], [2, 3]]) is False
    assert s.canAttendMeetings([[1, 3], [3, 5], [5, 7]]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Overlapping meetings | Basic failure case |
| Non-overlapping meetings | Basic success case |
| Touching endpoints | Confirms equality is allowed |
| Empty input | No meetings means no conflict |
| Nested intervals | Detects hidden overlap |
| Consecutive intervals | Valid chronological scheduling |