Employee Free Time

Employee Free Time

1. What is this problem about?

The Employee Free Time coding problem is a sophisticated scheduling challenge. You are given the working schedules of several employees, where each schedule is a list of non-overlapping intervals (start and end times). Your goal is to find the "common" free time—intervals during which no employees are working. These free time intervals must be finite and exist between the earliest start time and latest end time across all schedules.

2. Why is this asked in interviews?

Companies like Airbnb, Amazon, and Google ask the Employee Free Time interview question to test a candidate's ability to handle interval-based data and complex sorting. It’s a "Hard" problem because it requires merging multiple sorted lists and efficiently finding gaps. It tests your knowledge of data structures like Heaps (Priority Queues) or the Line Sweep algorithm, which are essential for building calendar systems, meeting schedulers, or resource allocators.

3. Algorithmic pattern used

The most effective Line Sweep or Merge Intervals pattern is used here. One approach is to flatten all intervals into a single list, sort them by start time, and then perform a standard interval merge. Any gap between the end of one merged interval and the start of the next represents common free time. Alternatively, since each employee's schedule is already sorted, a K-way Merge using a Min-Heap can be used to process intervals in chronological order more efficiently.

4. Example explanation

Let's say we have two employees:

• Employee 1: [[1, 3], [6, 7]]
• Employee 2: [[2, 4], [8, 10]]

Combined and sorted intervals: [1, 3], [2, 4], [6, 7], [8, 10].

1. Merge [1, 3] and [2, 4] -> [1, 4].
2. The next interval starts at 6. Gap between 4 and 6. Free time: [4, 6].
3. Merge [1, 4] with [6, 7] -> no overlap, current end is 7.
4. The next interval starts at 8. Gap between 7 and 8. Free time: [7, 8]. Final result: [[4, 6], [7, 8]].

5. Common mistakes candidates make

• Ignoring the "All Employees" condition: Forgetting that free time only exists if everyone is off. If one person is working, it's not "common" free time.
• Complexity Overload: Trying to use a nested loop to compare every interval with every other interval, resulting in $O(N^2)$ complexity, which is too slow.
• Handling Boundries: Failing to correctly identify the gaps between the merged intervals or including infinite intervals (like everything before the first shift).

6. Interview preparation tip

Master the "Merge Intervals" technique first. Once you are comfortable merging overlapping intervals, finding gaps becomes trivial. For an extra edge, learn how to use a Priority Queue to perform a K-way merge, as this is the most optimized way to handle pre-sorted input lists without fully re-sorting them.