Employee Free Time

Employee Free Time is a Meta interview problem involving arrays, sorting, heaps, and intervals. It requires finding common free time slots across multiple employees' schedules, where each schedule consists of non-overlapping, sorted work intervals.[3][4]

Problem Statement

We are given a list schedule of employees, where each employee has a list of non-overlapping Interval objects [start, end] sorted by start time with start < end. Return a list of finite intervals representing common, positive-length free time for all employees, also sorted by start time. Discard infinite intervals like [-inf, first_start] or [last_end, inf].[4][7][3]

Examples

Example 1

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: Employees work: Emp1 (1-2,5-6), Emp2 (1-3), Emp3 (4-10). Common finite free time is only.[3][4]

Example 2

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
Explanation: Merged busy times leave gaps at and when all are free.[5][6][7][9][3]

Example 3

Input: schedule = [[[2,4],[7,10]],[[1,5]],[[6,9]]]
Output: [[5,6]]
Explanation: Only one common finite free slot exists.[7]

Constraints

• 0 <= schedule.length <= 5000 (number of employees).
• For each employee: 0 <= schedule[i].length <= 1000 (intervals per employee).
• 0 <= start < end <= 10^8 for each interval.
• Intervals per employee are non-overlapping and sorted by start time.
• Total intervals N across all employees satisfies N ≤ 5000 * 1000, but typically smaller in practice.[1][2][3]