Employee Free Time - Leetcode Solution

The Employee Free Time problem on LeetCode is a problem that requires finding out time slots during which all employees are free. In this problem, each employee has a list of intervals during which they are busy, and the goal is to find out the list of time slots during which all employees are free.

To solve this problem, we will need to follow these steps:

Step 1: Create a list of all the time intervals during which the employees are busy.

Step 2: Sort the list of intervals by their start time.

Step 3: Merge the overlapping intervals to get a new list of non-overlapping intervals.

Step 4: Identify the gaps between the non-overlapping intervals. These gaps represent the time slots during which all employees are free.

Step 5: Return the list of these gaps.

Let's look at an example to help us understand how to solve this problem:

Assume we have three employees, each with their busy intervals:

Employee 1: [(1, 3), (6, 7)] Employee 2: [(2, 4)] Employee 3: [(2, 3), (9, 12)]

Step 1: We create a list of all the intervals during which the employees are busy.

[(1, 3), (2, 4), (2, 3), (6, 7), (9, 12)]

Step 2: We sort the list of intervals by their start time.

[(1, 3), (2, 3), (2, 4), (6, 7), (9, 12)]

Step 3: We merge the overlapping intervals to get a new list of non-overlapping intervals.

[(1, 4), (6, 7), (9, 12)]

Step 4: We identify the gaps between the non-overlapping intervals. These gaps represent the time slots during which all employees are free.

Gaps: (4, 6), (7, 9)

Step 5: We return the list of gaps.

[(4, 6), (7, 9)]

Here's the Python implementation for this approach:

def employeeFreeTime(schedule: List[List[Tuple[int, int]]]) -> List[Tuple[int, int]]:
    intervals = []
    for employee in schedule:
        for interval in employee:
            intervals.append(interval)
    
    intervals.sort()
    
    merged_intervals = [intervals[0]]
    for interval in intervals:
        if interval[0] <= merged_intervals[-1][1]:
            merged_intervals[-1] = (merged_intervals[-1][0], max(merged_intervals[-1][1], interval[1]))
        else:
            merged_intervals.append(interval)
    
    free_time = []
    for i in range(1, len(merged_intervals)):
        free_time.append((merged_intervals[i-1][1], merged_intervals[i][0]))
    
    return free_time

In this approach, we first create a list of all the intervals during which the employees are busy. We then sort this list by start time and merge overlapping intervals to get a new list of non-overlapping intervals. Finally, we find the gaps between the non-overlapping intervals and return them as the list of time slots during which all employees are free.

1