Leetcode 759. Employee Free Time

Problem

You are given a list of employee work schedules. Each employee has a list of non-overlapping time intervals representing when they are working. Each interval is represented as a pair of integers [start, end] where start < end.

Your task is to find all the time intervals when all employees are simultaneously free. Return these free time intervals in sorted order.

Requirements

1. Return a list of intervals representing times when no employee is working
2. The output intervals should be sorted by start time
3. Each employee's individual schedule is already sorted and contains non-overlapping intervals
4. Include only finite intervals (bounded gaps between work periods)

Constraints

• 1 ≤ number of employees ≤ 50
• 1 ≤ number of intervals per employee ≤ 50
• 0 ≤ start < end ≤ 10^8
• Each employee's schedule is sorted and non-overlapping
• Time complexity target: O(N log N) where N is total number of intervals
• Space complexity target: O(N)

Examples

Example 1:

Input: schedule = [[[1,3],[4,6]], [[2,4],[7,9]]] Output: [[6,7]] Explanation: Employee 1 works: [1,3] and [4,6] Employee 2 works: [2,4] and [7,9] Merging all busy times: [1,6] and [7,9] Free time when all are available: [6,7]

Example 2:

Input: schedule = [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]] Output: [[5,6],[7,9]] Explanation: Employee 1 works: [1,3], [6,7] Employee 2 works: [2,4] Employee 3 works: [2,5], [9,12] Merging all busy times: [1,5], [6,7], [9,12] Free intervals: [5,6] and [7,9]

Example 3:

Input: schedule = [[[1,10]], [[2,8]], [[3,6]]] Output: [] Explanation: All intervals overlap into one continuous period [1,10], so there are no gaps.

Hint 1: Flattening the Problem Think about how to convert this multi-employee problem into a simpler single-list problem. Can you combine all intervals from all employees into one unified collection?

Hint 2: Merge Then Find Gaps After collecting all working intervals from all employees, sort them and merge overlapping intervals. The gaps between merged intervals are the free times.

Hint 3: Alternative Approach with Events Consider using a sweep-line technique: treat each interval start and end as events. Track how many employees are working at any point. When the count drops to zero, you've found a free interval.

Full Solution `` Solution Explanation:

The key insight is to transform this multi-employee problem into a single interval merging problem:

1. Flatten: Combine all work intervals from all employees into a single list. Since we want to find when everyone is free, we need to know when anyone is busy.
2. Sort: Sort all intervals by their start time to prepare for merging.
3. Merge: Iterate through sorted intervals and merge any that overlap. Two intervals [a,b] and [c,d] overlap if b >= c. When merging, we extend the end time to cover both intervals.
4. Find Gaps: After merging, any gap between consecutive merged intervals represents a time when no one is working (everyone is free).

Time Complexity: O(N log N) where N is the total number of intervals across all employees. Sorting dominates the complexity.

Space Complexity: O(N) for storing the flattened intervals and merged results.

Alternative Approach: A sweep-line algorithm using a min-heap can also solve this problem by processing interval endpoints in order and tracking the number of active workers at each point.