Is Employee Free Time easy or hard?

Employee Free Time is classified as a Hard problem because it combines multiple concepts: interval merging, handling multiple sorted lists, and detecting gaps between merged intervals. The core logic becomes manageable once you recognize it as a merge-intervals pattern.

Employee Free Time Python/Java solution

Python and Java implementations typically flatten all intervals into a list, sort by start time, and perform interval merging. Python uses list sorting and iteration, while Java often uses a List with Collections.sort and interval comparison logic.

How to solve Employee Free Time in O(n)?

Pure O(n) time is not possible unless the intervals are already globally sorted. If all intervals from every employee are pre-sorted by start time, you can scan them once and detect gaps between merged intervals in linear time. Otherwise, sorting or heap merging introduces a logarithmic factor.

What is the best approach for Employee Free Time?

The interval merging approach is the most common solution. Flatten all employee intervals, sort them by start time, merge overlapping intervals, then return the gaps between merged intervals. This runs in O(N log N) time and O(N) space, where N is the total number of intervals.

Is Employee Free Time asked at Google/Amazon/Meta?

Employee Free Time is a well-known interval problem and appears in interview prep sets used by companies like Google, Amazon, and Meta. It tests understanding of interval merging, sorting, and heap-based multi-list merging patterns.

What data structure is used in Employee Free Time?

The most common structures are arrays or lists for storing intervals and sorting them. An optimized solution may use a min heap (priority queue) to perform a k-way merge across employee schedules while tracking the earliest start times.

What is the time complexity of Employee Free Time?

The typical solution runs in O(N log N) time due to sorting all intervals before merging them. A heap-based k-way merge optimization can achieve O(N log K) time where K is the number of employees. Space complexity is usually O(N) for storing intervals or O(K) for the heap.

Description Hints 1 Solution Video 15:37

759. Employee Free Time

Hard72.9% acceptance12 companiesPremium elsewhere, free here

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10^8

Asked at 12 companies

Citadel Airbnb Intuit Amazon Apple Roblox Pinterest

Google Tiktok Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Take all the intervals and do an "events" (or "line sweep") approach - an event of (x, OPEN) increases the number of active intervals, while (x, CLOSE) decreases it. Processing in sorted order from left to right, if the number of active intervals is zero, then you crossed a region of common free time.

15:37

Still stuck?Read the written solution, or watch a walkthrough.

Open solution