> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/merge-intervals/employee-free-time.md).

# Employee Free Time

## Problem

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.

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

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MR19CG99Y8ve_a-2iJ7%2F-MR1CDvuxo_Qc2QKSU50%2FScreen%20Shot%202021-01-14%20at%2011.42.35%20AM.png?alt=media\&token=cdfbea1c-6292-40b1-ad3e-bc381cf0c3c2)

### Thought Process

* This question is really similar to merge intervals except instead of merging them we find where they do not overlap

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MR19CG99Y8ve_a-2iJ7%2F-MR1CiE6SY11vHW3PVCk%2FIMG_B0BDE3C17CD6-1.jpeg?alt=media\&token=5fbc2b62-d1a8-42b0-b863-260d68e9a1c7)

## Solution

```
"""
# 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]':
        
        if not schedule:
            return []
        
        intervals = []
        
        for employee in schedule:
            for interval in employee:
                intervals.append([interval.start, interval.end])
        
        result = []
        #or you can just do the normal sort function
        intervals.sort(key = lambda x:x[0])
        print(intervals)

        lastEnd = intervals[0][1] 
        for i in range(1, len(intervals)):
            currStart = intervals[i][0]
            currEnd = intervals[i][1]
            if currStart > lastEnd:
                result.append(Interval(lastEnd, currStart))
            lastEnd = max(lastEnd, currEnd)
        
        return result
```

## Time Complexity

* **Time:** O(n log n) because we have to sort the intervals
* **Space:** O(n) since we're storing intervals