# Employee Free Time

### Clarify the problem

- The problem is to find the free time slots of all employees in a schedule.
- The input is a list of schedules for each employee, where each schedule is a list of intervals representing their working hours.
- The output should be a list of free time slots common to all employees.

### Analyze the problem

- We need to find the time slots where no employee is scheduled to work.
- To find the common free time slots, we can merge the intervals of each employee's schedule and then find the gaps between them.

### Design an algorithm

- Merge intervals of each employee's schedule:
- Sort the intervals based on the start time.
- Initialize an empty list called "merged" to store the merged intervals.
- Iterate through each interval:
- If "merged" is empty or the current interval does not overlap with the last merged interval, add the current interval to "merged".
- Otherwise, update the end time of the last merged interval to be the maximum of the current interval's end time and the last merged interval's end time.

- Find the free time slots:
- Initialize an empty list called "free_slots".
- Iterate through the merged intervals:
- If the next interval's start time is greater than the current interval's end time, it represents a free slot.
- Add the free slot (current interval's end time to next interval's start time) to "free_slots".

- If the next interval's start time is greater than the current interval's end time, it represents a free slot.

### Explain your approach

- First, we will merge the intervals of each employee's schedule to identify the occupied time slots.
- Then, we will iterate through the merged intervals and find the free time slots between them.
- By considering the intervals in sorted order, we can easily determine the gaps where no employee is scheduled.

### Write clean and readable code

```
def employeeFreeTime(schedule):
merged = mergeIntervals(schedule)
return findFreeSlots(merged)
def mergeIntervals(schedule):
merged = []
schedule.sort(key=lambda x: x[0]) # Sort based on start time
for interval in schedule:
if not merged or interval[0] > merged[-1][1]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
def findFreeSlots(merged):
free_slots = []
for i in range(1, len(merged)):
start = merged[i-1][1]
end = merged[i][0]
if start < end:
free_slots.append([start, end])
return free_slots
```

### Test your code

- Let's test the code with some test cases:

```
# Test case 1
schedule = [[[1, 3], [6, 7]], [[2, 4]], [[2, 5], [9, 12]]]
# Employee 1: [1, 3], [6, 7]
# Employee 2: [2, 4]
# Employee 3: [2, 5], [9, 12]
# Merged intervals: [1, 5], [6, 7], [9, 12]
# Free slots: [5, 6], [7, 9]
print(employeeFreeTime(schedule)) # Output: [[5, 6], [7, 9]]
# Test case 2
schedule = [[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]
# Employee 1: [1, 2], [5, 6]
# Employee 2: [1, 3]
# Employee 3: [4, 10]
# Merged intervals: [1, 3], [4, 10]
# Free slots: [3, 4]
print(employeeFreeTime(schedule)) # Output: [[3, 4]]
```

### Optimize if necessary

- The current solution has a time complexity of O(nlogn), where n is the total number of intervals in all employees' schedules. This is because we need to sort the intervals before merging them.
- The space complexity is O(n), where n is the total number of intervals in all employees' schedules. This is because we need to store the merged intervals.

### Handle error cases

- The code assumes that the input is a valid list of schedules, where each schedule is a list of intervals. If the input is invalid, the behavior of the code may not be as expected.
- The code does not handle cases where the intervals are not in ascending order or if the end time of an interval is before its start time.

### Discuss complexity analysis

- The time complexity of the solution is O(nlogn) because we sort the intervals before merging them. The merging process takes linear time O(n), where n is the total number of intervals.
- The space complexity is O(n) because we need to store the merged intervals, which can be at most the same size as the input.
- The algorithm efficiently finds the free time slots by merging and analyzing the intervals, minimizing unnecessary comparisons and iterations.