Skip to main content
Talentd

Employee Free Time - Solution & Explanation

HardPremiumFree on FleetCodeArraySortingHeap (Priority Queue)7 min readAsked at: Amazon, Microsoft, Apple +9
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Each employee has a sorted list of non-overlapping working intervals. The goal is to return all finite intervals where every employee is simultaneously free. In practice, you need to combine multiple schedules and detect the gaps between merged working intervals.

Approach 1: Brute Force Flatten + Sort (O(N log N) time, O(N) space)

Collect every interval from every employee into a single list. Sort the intervals by start time using a standard sorting step. Then iterate through the sorted intervals while maintaining the latest merged end time. If the next interval starts after the current end, that gap represents a block of shared free time. This approach works because once intervals are globally ordered, detecting gaps becomes a simple linear scan.

Approach 2: Interval Merging (O(N log N) time, O(N) space)

This is the most common implementation. Flatten all intervals, sort by start time, and merge overlapping intervals using the classic array-based interval merging pattern. Maintain a merged interval list and extend the current interval whenever overlaps occur. After merging, iterate through the merged list and return the gaps between consecutive intervals. The key insight: free time appears only between merged busy intervals shared across all employees.

Approach 3: K-Way Merge with Min Heap (O(N log K) time, O(K) space)

Instead of flattening everything, treat each employee schedule as a sorted stream and perform a k-way merge using a heap (priority queue). Push the first interval from each employee into a min-heap keyed by start time. Repeatedly pop the earliest interval and track the maximum end time seen so far. If the next interval starts after that end, you found a shared free slot. Then push the next interval from the same employee into the heap. This reduces sorting cost because the heap only manages K employees at once.

Recommended for interviews: The interval merging approach is typically expected. It shows you recognize the classic "merge intervals" pattern and can apply it after flattening schedules. Mentioning the heap-based k-way merge demonstrates deeper knowledge of multi-stream merging and improves scalability when many employees are involved. Starting with the brute-force flattening idea shows understanding, but the optimized merging or heap approach signals strong algorithmic reasoning.

Solution

We can merge all employees' working time intervals into a single list, then sort and merge the overlapping intervals. Finally, we traverse the merged interval list to find the free time periods between adjacent intervals.

The time complexity is O(mn log(mn)) and the space complexity is O(mn), where m is the number of employees and n is the number of working intervals per employee.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Flatten + SortO(N log N)O(N)Simple implementation when total intervals are manageable
Interval MergingO(N log N)O(N)General case and most common interview solution
K-Way Merge with HeapO(N log K)O(K)Large number of intervals but relatively few employees

Video Solution

LeetCode 759. Employee Free Time • Happy Coding • 8,705 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Employee Free Time with our built-in code editor and test cases.

Practice on FleetCode
Previous

Interval List Intersections

Next

Merge Intervals