## 759. Employee Free Time

We are given a list `schedule` of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping `Intervals`, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

```Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.
```

Example 2:

```Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
```

(Even though we are representing `Intervals` in the form `[x, y]`, the objects inside are `Intervals`, not lists or arrays. For example, `schedule[0][0].start = 1, schedule[0][0].end = 2`, and `schedule[0][0][0]` is not defined.)

Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. `schedule` and `schedule[i]` are lists with lengths in range `[1, 50]`.
2. `0 <= schedule[i].start < schedule[i].end <= 10^8`.

b'
\n\n

#### Approach #1: Events (Line Sweep) [Accepted]

\n

Intuition

\n

If some interval overlaps any interval (for any employee), then it won\'t be included in the answer. So we could reduce our problem to the following: given a set of intervals, find all places where there are no intervals.

\n

To do this, we can use an "events" approach present in other interval problems. For each interval `[s, e]`, we can think of this as two events: `balance++` when `time = s`, and `balance--` when `time = e`. We want to know the regions where `balance == 0`.

\n

Algorithm

\n

For each interval, create two events as described above, and sort the events. Now for each event occuring at time `t`, if the `balance` is `0`, then the preceding segment `[prev, t]` did not have any intervals present, where `prev` is the previous value of `t`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the number of intervals across all employees.

\n
• \n
• \n

Space Complexity: .

\n
• \n
\n
\n

#### Approach #2: Priority Queue [Accepted]

\n

Intuition

\n

Say we are at some time where no employee is working. That work-free period will last until the next time some employee has to work.

\n

So let\'s maintain a heap of the next time an employee has to work, and it\'s associated job. When we process the next time from the heap, we can add the next job for that employee.

\n

Algorithm

\n

Keep track of the latest time `anchor` that we don\'t know of a job overlapping that time.

\n

When we process the earliest occurring job not yet processed, it occurs at time `t`, by employee `e_id`, and it was that employee\'s `e_jx`\'th job. If `anchor < t`, then there was a free interval `Interval(anchor, t)`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the number of employees, and is the number of jobs across all employees. The maximum size of the heap is , so each push and pop operation is , and there are such operations.

\n
• \n
• \n

Space Complexity: in additional space complexity.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'