Practice/Google/Leetcode 759. Employee Free Time

Leetcode 759. Employee Free Time

CodingMust

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.