Problem Description

The Employee Free Time problem asks you to find the common free intervals across multiple employees, given each employee's working schedule. Each employee's schedule is a list of non-overlapping intervals representing the times they are working. The goal is to return a list of finite intervals representing the times when all employees are free (i.e., not working).

• Each employee's schedule is a list of intervals [start, end] where start < end, and intervals do not overlap or touch.
• Input: schedule is a list of lists of intervals. Each inner list is one employee's schedule.
• Output: A list of intervals representing times when all employees are free. Intervals should be finite, non-overlapping, and sorted.
• Constraints: All intervals are within a single day, and at least one employee is present.

Thought Process

At first, you might consider brute-forcing by checking every possible time and seeing if all employees are free at that moment. However, this is inefficient and unnecessary. Instead, realize that the problem is about merging intervals: if we know when employees are busy, we can merge all their busy times together, and then the gaps between those merged intervals are the free times.

Conceptually, this is similar to merging calendar events from multiple people and finding the gaps when no one is in a meeting. The challenge is efficiently merging all intervals and then finding the gaps between them.

Solution Approach

The optimal approach is to:

1. Flatten all intervals: Combine all employees' schedules into a single list of intervals.
2. Sort intervals: Sort this list by the start time of each interval.
3. Merge overlapping intervals: Iterate through the sorted list and merge any intervals that overlap or touch.
4. Find gaps: After merging, the gaps between the end of one interval and the start of the next represent the times when all employees are free.

We use sorting because it allows us to process intervals in order and easily merge overlaps. Merging is efficient because we only need to look at the previous interval to see if there is overlap.

• We can use a list to keep track of merged intervals.
• When finding gaps, we compare the end of the previous merged interval to the start of the next merged interval.

Example Walkthrough

Suppose we have the following input:

  schedule = [
    [[1,2],[5,6]],
    [[1,3]],
    [[4,10]]
  ]
  

1. Flatten: All intervals: [[1,2],[5,6],[1,3],[4,10]]
2. Sort: [[1,2],[1,3],[4,10],[5,6]] → after sorting by start: [[1,2],[1,3],[4,10],[5,6]]
3. Merge:
   • Start with [1,2]
   • [1,3] overlaps with [1,2] → merge to [1,3]
   • [4,10] does not overlap with [1,3] → add [4,10]
   • [5,6] overlaps with [4,10] → merge to [4,10]
   Final merged intervals: [[1,3],[4,10]]
4. Find gaps:
   • Between [1,3] and [4,10] is [3,4]
   Output: [[3,4]]

Code Implementation

# Definition for an Interval.
# class Interval:
#     def __init__(self, start: int, end: int):
#         self.start = start
#         self.end = end

def employeeFreeTime(schedule):
    # Flatten all intervals
    intervals = [iv for emp in schedule for iv in emp]
    # Sort intervals by start time
    intervals.sort(key=lambda x: x.start)
    # Merge intervals
    merged = []
    for iv in intervals:
        if not merged or merged[-1].end < iv.start:
            merged.append(iv)
        else:
            merged[-1].end = max(merged[-1].end, iv.end)
    # Find gaps
    res = []
    for i in range(1, len(merged)):
        if merged[i-1].end < merged[i].start:
            res.append(Interval(merged[i-1].end, merged[i].start))
    return res
      

/*
// Definition for an Interval.
class Interval {
public:
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};
*/

vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
    vector<Interval> intervals;
    for (auto& emp : schedule)
        for (auto& iv : emp)
            intervals.push_back(iv);
    sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b) {
        return a.start < b.start;
    });
    vector<Interval> merged;
    for (auto& iv : intervals) {
        if (merged.empty() || merged.back().end < iv.start)
            merged.push_back(iv);
        else
            merged.back().end = max(merged.back().end, iv.end);
    }
    vector<Interval> res;
    for (int i = 1; i < merged.size(); ++i) {
        if (merged[i-1].end < merged[i].start)
            res.push_back(Interval(merged[i-1].end, merged[i].start));
    }
    return res;
}
      

/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;
    public Interval() { start = 0; end = 0; }
    public Interval(int s, int e) { start = s; end = e; }
}
*/

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    List<Interval> intervals = new ArrayList<>();
    for (List<Interval> emp : schedule)
        intervals.addAll(emp);
    intervals.sort((a, b) -> a.start - b.start);
    List<Interval> merged = new ArrayList<>();
    for (Interval iv : intervals) {
        if (merged.isEmpty() || merged.get(merged.size()-1).end < iv.start)
            merged.add(iv);
        else
            merged.get(merged.size()-1).end = Math.max(merged.get(merged.size()-1).end, iv.end);
    }
    List<Interval> res = new ArrayList<>();
    for (int i = 1; i < merged.size(); ++i) {
        if (merged.get(i-1).end < merged.get(i).start)
            res.add(new Interval(merged.get(i-1).end, merged.get(i).start));
    }
    return res;
}
      

/**
 * // Definition for an Interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */

/**
 * @param {Interval[][]} schedule
 * @return {Interval[]}
 */
var employeeFreeTime = function(schedule) {
    let intervals = [];
    for (let emp of schedule)
        for (let iv of emp)
            intervals.push(iv);
    intervals.sort((a, b) => a.start - b.start);
    let merged = [];
    for (let iv of intervals) {
        if (merged.length === 0 || merged[merged.length-1].end < iv.start)
            merged.push(iv);
        else
            merged[merged.length-1].end = Math.max(merged[merged.length-1].end, iv.end);
    }
    let res = [];
    for (let i = 1; i < merged.length; ++i) {
        if (merged[i-1].end < merged[i].start)
            res.push(new Interval(merged[i-1].end, merged[i].start));
    }
    return res;
};
      

Time and Space Complexity

• Brute-force approach: If you checked each possible time, time complexity would be O(T * N), where T is the number of possible times and N is the number of employees. This is not efficient.
• Optimized approach:
  • Flattening all intervals takes O(N), where N is the total number of intervals.
  • Sorting intervals takes O(N log N).
  • Merging intervals and finding gaps is O(N).

  So, the overall time complexity is O(N log N) due to sorting.

  The space complexity is O(N) for storing all intervals and the merged list.

Summary

The Employee Free Time problem is elegantly solved by merging all employees' working intervals and then finding the gaps between those merged intervals. This approach leverages sorting and interval merging, which are efficient and easy to implement. The key insight is to shift from checking all possible times to simply working with interval endpoints, making the solution both concise and optimal.