Employee Free Time

Employee Free Time is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Interval Merging/Scheduling subpattern.

Problem statement

You are given a list schedule where schedule[i] represents the list of non-overlapping, sorted intervals [start, end] during which the i-th employee is working. Each employee may have multiple working intervals, and intervals are represented as closed on the left and open on the right: [start, end).

Your task is to find the finite intervals during which all employees are free—that is, periods when none of the employees are working. The free time intervals should not include any time before the earliest start time or after the latest end time among all employees' schedules.

Return a list of intervals representing the common free time, sorted in ascending order by start time. Each interval should be represented as a list [start, end].

Topics and companies

Topics: Array, Line Sweep, Sorting, Heap (Priority Queue).

Reported in interviews at DoorDash, Pinterest, Amazon, Intuit, Oracle, Bloomberg, Wayfair.

How to practise Employee Free Time on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N log N), where N is the total number of intervals. Flattening is O(N), sorting is O(N log N), merging is O(N), and finding gaps is O(N). time and O(N), for storing all intervals and the merged intervals. space.

Open Employee Free Time in the code editor, or read the Employee Free Time editorial for a worked solution with its approach and complexity analysis.

Where Employee Free Time sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Interval Merging/Scheduling subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Employee Free Time

Other problems that use the same Interval Merging/Scheduling and Greedy Patterns techniques:

• Interval List Intersections — Medium, same subpattern
• Assign Cookies — Easy, same pattern
• Candy — Hard, same pattern
• Distant Barcodes — Medium, same pattern
• Divide Intervals Into Minimum Number of Groups — Medium, same pattern
• Gas Station — Medium, same pattern