Employee Free Time

Try to solve the Employee Free Time problem.

We'll cover the following

Statement#

You’re given a list containing the schedules of multiple employees. Each person’s schedule is a list of non-overlapping intervals in sorted order. An interval is specified with the start and end time, both being positive integers. Your task is to find the list of finite intervals representing the free time for all the employees.

Constraints:

  • 1≤1 \leq schedule.length , schedule[i].length ≤50\leq 50

  • 0≤0 \leq interval.start < interval.end ≤108\leq 10^8, where interval is any interval in the list of schedules.

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Employee Free Time

1

From the given list of employee schedules, find the list of intervals representing the free time for all the employees.

[[[3, 5], [8, 10]], [[4, 6], [9, 12]], [[5, 6], [8, 10]]]

A)

[[2, 8]]

B)

[[6, 8]]

C)

[[2, 6]]

D)

[[4, 6]]

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize a heap and push the first interval of each employee onto the heap.

Set the previous interval as the start time of the first interval.

Repeatedly pop the smallest interval from the heap and compare it with the previous interval.

If the current starting time is greater than the previous interval, add it to the result list.

Update the previous interval as the maximum of the previous interval and end time of the current interval.

Push additional intervals of the current employee onto the heap if it exists.

When the heap becomes empty, return the result list.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided the definition of the Interval class in the other file. You may add functionality to this class if you wish.

Python
main.py
interval.py
Input #1
Employee Free Time

Solution: Insert Interval

Solution: Employee Free Time