Module 3 · Scheduling Pattern

Employee Free Time

HardProblem 6 of 12 10 min read ~32 min to solve LeetCode

IntervalsSortingMergeGreedyScheduling

Asked atAirbnbAmazonGoogleMicrosoftMeta

Problem Statement

You are given each employee's schedule as a list of non-overlapping busy intervals. Return all finite intervals during which every employee is free.

Input

A list schedule, where schedule[i] is the sorted busy schedule for employee i.

Output

A list of finite intervals where all employees are free.

Constraints

•1 <= schedule.length <= 50
•1 <= schedule[i].length <= 50
•0 <= interval.start < interval.end <= 10^8
•Each employee schedule is sorted and non-overlapping

Examples

Example 1

Input:

schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Output: [[3,4]]

Explanation: The merged busy time is **[1,3]** and **[4,10]**. The only finite gap between those busy blocks is **[3,4]**.

Example 2

Input:

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

Output: [[5,6],[7,9]]

Explanation: Flattening and merging all busy intervals gives **[1,5]**, **[6,7]**, and **[9,12]**. The gaps are **[5,6]** and **[7,9]**.

Learning Objectives

Invert the question from common free time to the union of busy time.
Flatten multiple employee schedules into one global interval list.
Merge overlapping busy intervals before looking for free gaps.
Exclude unbounded time before the first busy block and after the last busy block.

Intuition

Pattern Recognition

The signal is free for every employee. The tempting but messy route is to compute each person's free intervals and intersect them. The cleaner route is the inverse: if anyone is busy, the group is not free. So first build the global union of all busy intervals.

Once all busy intervals are flattened and sorted by start time, the problem becomes Merge Intervals with one extra observation. Every gap between two merged busy blocks is common free time. Touching blocks such as [1,3] and [3,5] do not create free time because the gap length is zero.

Common mistakes

×Returning free time for one employee instead of time free for every employee.
×Looking for gaps before merging busy intervals, which creates false free windows inside someone else's meeting.
×Treating touching busy intervals as a positive-length free interval.
×Adding time before the first busy interval or after the last busy interval even though the problem asks for finite common free time.

Algorithm Explanation

Key idea

Flatten every employee's busy intervals into one list, sort that list by start time, and merge it as the union of busy time. Whenever the next busy interval starts after the current merged busy end, the gap [current end, next start] is free for everyone. Then begin a new busy block from that next interval.

Interval walkthrough

Use schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]. Flattened and sorted, the busy intervals are [1,2], [1,3], [4,10], [5,6]. Carry busy block [1,2]. Seeing [1,3] overlaps it, so extend the block to [1,3]. Seeing [4,10] starts after 3, so the number line has a free gap [3,4]. Start the next busy block as [4,10]. Finally [5,6] lies inside that block, so no new gap appears.

Algorithm

Create an empty list of all busy intervals.
Append every employee interval into that list.
Sort the flattened list by start time.
Track the end of the current merged busy block.
For each next interval, if its start is greater than the current busy end, record [current end, next start] as free time and reset the busy end to that interval's end.
Otherwise, merge by extending the busy end to the larger end.
Return all recorded gaps.

Solutions

Solution: Flatten, sort, and merge busy time

When to prefer this:

Use this when schedules are available as lists and you only need the common finite free intervals, not an online data structure.

Turn all employee schedules into one global busy list. After sorting by start time, merge overlapping busy intervals and emit the gaps between merged blocks as the common free time.

Step-by-step

Add every employee interval into busyIntervals.
Sort busyIntervals by start.
Initialise currentEnd from the first busy interval.
For each next interval, compare its start with currentEnd.
If start > currentEnd, append a new free interval [currentEnd, start] and move currentEnd to that interval's end.
Otherwise, merge by setting currentEnd to the larger of the two ends.
Return the list of free intervals.

Time

O(n log n)

Space

O(n)

Here **n** is the total number of busy intervals across all employees. Flattening takes O(n), sorting dominates, and the output list can also hold O(n) gaps.

Java implementation

Loading…

Dry Run

Sample input

schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]. After flattening and sorting, scan [1,2], [1,3], [4,10], [5,6].

next busy interval	current busy end before	action	free time so far
[1,3]	2	overlaps the current busy block, extend end to 3	[]
[4,10]	3	start is after 3, record [3,4]	[[3,4]]
[5,6]	10	covered by current busy block, keep end 10	[[3,4]]

Only gaps between merged busy blocks are returned. The interval [5,6] is one employee's busy time inside [4,10], so it cannot create common free time.

Interview Tips

Frame the problem as an inversion: common free time is the complement of the union of all busy time. That one sentence usually unlocks the solution. Be explicit that only finite gaps between merged busy blocks are returned, and that start == currentEnd is not a free interval.

Likely follow-ups

How would you solve this with a min-heap over each employee's next interval instead of flattening first?
How would you return only free intervals of at least a given duration?
How would you handle streaming schedule updates during the day?
How would the output change if the workday had fixed boundaries such as 9 to 17?

Key Takeaways

Common free time is found by merging everyone else's busy time first.
A gap appears only when the next busy start is greater than the merged busy end.
Touching busy intervals do not produce a positive-length free interval.
Do not include unbounded time before the first busy block or after the last busy block.

Reusable template: Busy-union inversion: flatten all occupied intervals, merge them into disjoint busy blocks, and return the finite gaps between those blocks.