Employee Free Time

Problem Statement

Given the work schedules of all employees (a list of lists of intervals), find the common free time across all employees — the gaps in which nobody is working.

Input

A list of schedules, one per employee. Each employee’s schedule is a list of non-overlapping busy intervals.

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

Output

The list of free intervals — gaps where no employee is working — returned in sorted order.

[[3,4]]

Constraints

• 1 ≤ schedule.length ≤ 50 (employees)
• 1 ≤ schedule[i].length ≤ 50 (intervals per employee)
• 0 ≤ schedule[i][j].start < schedule[i][j].end ≤ 10⁸
• Each employee’s intervals are pairwise disjoint and sorted.

Intuition

This problem reduces to “Merge Intervals” + “find the gaps.” Flatten every schedule into one big list → sort by start → merge overlapping intervals → the gaps between consecutive merged intervals are the common free time.

Input schedules:
  A: [1,2]      [5,6]
  B: [1,3]
  C:            [4,10]
 
Flatten + sort:  [1,2] [1,3] [4,10] [5,6]
Merge:           [1,3]  [4,10]          ← [5,6] swallowed by [4,10]
Gaps:                ^^^
                     [3,4]   ← common free time

Solution

def employeeFreeTime(schedule):
    # Flatten all intervals
    all_intervals = []
    for employee in schedule:
        all_intervals.extend(employee)
 
    all_intervals.sort(key=lambda x: x[0])
 
    # Merge
    merged = [all_intervals[0]]
    for interval in all_intervals[1:]:
        if interval[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], interval[1])
        else:
            merged.append(interval)
 
    # Gaps = free time
    free = []
    for i in range(1, len(merged)):
        free.append([merged[i-1][1], merged[i][0]])
 
    return free

function employeeFreeTime(schedule: number[][][]): number[][] {
    const all: number[][] = schedule.flat();
    all.sort((a, b) => a[0] - b[0]);
 
    const merged: number[][] = [all[0]];
    for (let i = 1; i < all.length; i++) {
        const last = merged[merged.length - 1];
        if (all[i][0] <= last[1]) {
            last[1] = Math.max(last[1], all[i][1]);
        } else {
            merged.push([...all[i]]);
        }
    }
 
    const free: number[][] = [];
    for (let i = 1; i < merged.length; i++) {
        free.push([merged[i - 1][1], merged[i][0]]);
    }
 
    return free;
}

Complexity

Edge Case Thinking