# LeetCode 759: Employee Free Time

## Problem Restatement

We are given the working schedules of several employees.

Each employee has a list of non-overlapping intervals, sorted by start time.

Each interval represents a time when that employee is busy.

We need to return all finite, positive-length intervals when every employee is free.

We do not include infinite intervals before the earliest busy time or after the latest busy time.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `schedule`, a list of employee schedules |
| Schedule item | Each employee schedule is a sorted list of busy intervals |
| Output | A sorted list of common free-time intervals |
| Rule | A free interval must have positive length |
| Excluded | Infinite free time before all work and after all work |

LeetCode uses an `Interval` class:

```python
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
```

Example function shape:

```python
def employeeFreeTime(schedule: list[list[Interval]]) -> list[Interval]:
    ...
```

## Examples

Example 1:

```python
schedule = [
    [Interval(1, 2), Interval(5, 6)],
    [Interval(1, 3)],
    [Interval(4, 10)],
]
```

Output:

```python
[Interval(3, 4)]
```

The combined busy intervals are:

```text
[1,2], [5,6], [1,3], [4,10]
```

After merging busy time:

```text
[1,3], [4,10]
```

The gap between them is:

```text
[3,4]
```

That is the only finite common free time.

Example 2:

```python
schedule = [
    [Interval(1, 3), Interval(6, 7)],
    [Interval(2, 4)],
    [Interval(2, 5), Interval(9, 12)],
]
```

Output:

```python
[Interval(5, 6), Interval(7, 9)]
```

All employees are busy during the merged intervals:

```text
[1,5], [6,7], [9,12]
```

The finite gaps are:

```text
[5,6], [7,9]
```

## First Thought: Check Every Time Unit

A direct idea is to mark every time unit as busy or free.

But interval endpoints can be as large as `10^8`.

So marking every possible time value would be wasteful.

We only care about interval boundaries.

That means this is an interval merging problem.

## Key Insight

All employees are free exactly when no employee is busy.

So instead of trying to compute free time directly, we first compute the union of all busy intervals.

Then common free time is simply the gaps between merged busy intervals.

For example:

```text
Employee busy intervals:
[1,3], [6,7], [2,4], [2,5], [9,12]
```

Sorted:

```text
[1,3], [2,4], [2,5], [6,7], [9,12]
```

Merged busy intervals:

```text
[1,5], [6,7], [9,12]
```

Free intervals:

```text
[5,6], [7,9]
```

## Flatten All Schedules

The input is grouped by employee.

For merging, employee identity does not matter. Busy time from any employee blocks common free time.

So we flatten all intervals into one list:

```python
intervals = []

for employee in schedule:
    for interval in employee:
        intervals.append(interval)
```

Then sort by start time:

```python
intervals.sort(key=lambda interval: interval.start)
```

## Merge Busy Intervals and Record Gaps

After sorting, scan from left to right.

Keep the farthest busy end seen so far:

```python
prev_end
```

For each interval:

1. If `interval.start > prev_end`, there is a free gap:

```python
[prev_end, interval.start]
```

2. Then update:

```python
prev_end = max(prev_end, interval.end)
```

If `interval.start <= prev_end`, the interval overlaps or touches the current busy range, so there is no positive-length free time between them.

## Algorithm

1. Flatten all employee intervals into one list.
2. Sort all intervals by start time.
3. Set `prev_end` to the end of the first interval.
4. For each later interval:
   1. If its start is greater than `prev_end`, append a free interval `[prev_end, start]`.
   2. Update `prev_end` to the maximum of `prev_end` and the current interval end.
5. Return the free intervals.

## Correctness

Every employee busy interval is added to the flattened list. Therefore, the flattened list contains exactly all times when at least one employee is busy.

After sorting by start time, scanning the intervals from left to right lets us maintain the merged busy region seen so far. The value `prev_end` is the right boundary of the current merged busy interval.

If the next interval starts at or before `prev_end`, it overlaps or touches the current busy region. There is no positive-length time gap where all employees are free, so the algorithm only extends `prev_end` if needed.

If the next interval starts after `prev_end`, then no busy interval covers the open time between `prev_end` and `interval.start`. Since all earlier busy intervals end no later than `prev_end`, and the next busy interval starts at `interval.start`, every employee is free during that finite positive-length interval. The algorithm appends exactly that gap.

Every finite common free interval must occur between two adjacent merged busy intervals. The algorithm records every such gap during the scan.

Therefore, the returned list contains exactly all finite positive-length intervals when all employees are free.

## Complexity

Let `N` be the total number of intervals across all employees.

| Metric | Value | Why |
|---|---|---|
| Time | `O(N log N)` | We sort all intervals |
| Space | `O(N)` | We store the flattened intervals and output |

## Implementation

```python
"""
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        intervals = []

        for employee in schedule:
            for interval in employee:
                intervals.append(interval)

        intervals.sort(key=lambda interval: interval.start)

        ans = []
        prev_end = intervals[0].end

        for interval in intervals[1:]:
            if interval.start > prev_end:
                ans.append(Interval(prev_end, interval.start))

            prev_end = max(prev_end, interval.end)

        return ans
```

## Code Explanation

We first flatten the nested schedule:

```python
intervals = []

for employee in schedule:
    for interval in employee:
        intervals.append(interval)
```

Once all busy intervals are in one list, we sort them:

```python
intervals.sort(key=lambda interval: interval.start)
```

Now intervals are processed in chronological order.

We start the merged busy range with the first interval:

```python
prev_end = intervals[0].end
```

Then we scan the remaining intervals:

```python
for interval in intervals[1:]:
```

If the next busy interval starts after `prev_end`, there is a gap:

```python
if interval.start > prev_end:
    ans.append(Interval(prev_end, interval.start))
```

The strict comparison matters.

If `interval.start == prev_end`, the gap has zero length, so it should not be included.

Then we update the right boundary of the current merged busy interval:

```python
prev_end = max(prev_end, interval.end)
```

Finally, the answer contains all finite common free intervals.

## Testing

For local testing, we can add a small helper to compare intervals.

```python
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end

def as_pairs(intervals: list[Interval]) -> list[list[int]]:
    return [[interval.start, interval.end] for interval in intervals]

def run_tests():
    s = Solution()

    schedule = [
        [Interval(1, 2), Interval(5, 6)],
        [Interval(1, 3)],
        [Interval(4, 10)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == [[3, 4]]

    schedule = [
        [Interval(1, 3), Interval(6, 7)],
        [Interval(2, 4)],
        [Interval(2, 5), Interval(9, 12)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == [[5, 6], [7, 9]]

    schedule = [
        [Interval(1, 5)],
        [Interval(2, 3)],
        [Interval(5, 8)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == []

    schedule = [
        [Interval(1, 2)],
        [Interval(4, 5)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == [[2, 4]]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Main example 1 | Confirms finite gap only |
| Main example 2 | Confirms multiple free intervals |
| Touching intervals | Zero-length gaps are excluded |
| Separate intervals | Basic gap detection |