Solution: Problem Challenge 3: Employee Free Time

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 3: Employee Free Time

Table of Contents

Contents are not accessible

Problem Statement

For ‘K’ employees, we are given a list of intervals representing each employee’s working hours. Our goal is to determine if there is a free interval which is common to all employees.

Example 1:

Input: Employee Working Hours=[[[1,3], [5,6]], [[2,3], [6,8]]]
Output: [3,5]
Explanation: All the employees are free between [3,5].

Example 2:

Input: Employee Working Hours=[[[1,3], [9,12]], [[2,4]], [[6,8]]]
Output: [4,6], [8,9]
Explanation: All employees are free between [4,6] and [8,9].

Example 3:

Input: Employee Working Hours=[[[1,3]], [[2,4]], [[3,5], [7,9]]]
Output: [5,7]
Explanation: All employees are free between [5,7].

Solution

This problem follows the Merge Intervals pattern.

Let’s take the above-mentioned example (2) and visually draw it:

Input: Employee Working Hours=[[[1,3], [9,12]], [[2,4]], [[6,8]]]
Output: [4,6], [8,9]

One simple solution can be to put all employees’ working hours in a list and sort them on the start time. Then we can iterate through the list to find the gaps.

Let’s dig deeper.

Sorting the intervals of the above example will give us:

[1,3], [2,4], [6,8], [9,12]

We can now iterate through these intervals, and whenever we find non-overlapping intervals (e.g., [2,4] and [6,8]), we can calculate a free interval (e.g., [4,6]). This algorithm will take $O(N * logN)$ time, where ‘N’ is the total number of intervals. This time is needed because we need to sort all the intervals. The space complexity will be O(N), which is needed for sorting.

Can we find a better solution?

Using a Heap to Sort the Intervals

One fact that we are not utilizing is that each employee list is individually sorted!

How about we take the first interval of each employee and insert it in a Min Heap. This Min Heap can always give us the interval with the smallest start time. Once we have the smallest start-time interval, we can then compare it with the next smallest start-time interval (again from the Heap) to find the gap. This interval comparison is similar to what we suggested in the previous approach.

Whenever we take an interval out of the Min Heap, we can insert the same employee’s next interval in the heap. This also means that we need to know which interval belongs to which employee.

Step-by-Step Algorithm

Initialize an empty list to store the result (free times).
Create a priority queue to keep track of intervals. This will help in managing intervals based on start times.
Add the first interval of each employee's schedule to the priority queue.
Set the previousInterval to the interval with the earliest start time (from the priority queue).
While the priority queue is not empty:
- Remove the interval with the earliest start time from the priority queue.
- Check if there is a gap between previousInterval and the current interval:
  - If there is a gap, add this gap to the result list.
  - Update previousInterval to the current interval.
- Otherwise (if they overlap), update the previousInterval to cover the current interval if needed.
- If the current employee has more intervals, add the next interval of this employee to the priority queue.
Return the result list containing all free times.

Algorithm Walkthrough

Using the input Employee Working Hours = [[[1, 3], [9, 12]], [[2, 4]], [[6, 8]]]:

Initialize result list: [].
Initialize priority queue with the first intervals of each employee: [(1, 3), (2, 4), (6, 8)], each represented as an EmployeeInterval object containing the interval, employee index, and interval index:
- Priority queue: [(1, 3, 0, 0), (2, 4, 1, 0), (6, 8, 2, 0)]
Set previousInterval to the interval with the earliest start time, (1, 3).
While the priority queue is not empty:
- Remove (1, 3, 0, 0) from the queue. Priority queue: [(2, 4, 1, 0), (6, 8, 2, 0)].
  - Check if there is a gap between previousInterval and the current interval (2, 4):
    - No gap, update previousInterval to (2, 4).
  - If employee 0 has more intervals, add next interval (9, 12) to the queue. Priority queue: [(2, 4, 1, 0), (6, 8, 2, 0), (9, 12, 0, 1)].
- Remove (2, 4, 1, 0) from the queue. Priority queue: [(6, 8, 2, 0), (9, 12, 0, 1)].
  - Check if there is a gap between previousInterval and the current interval (6, 8):
    - Gap found between (4, 6). Add this interval to result: result = [[4, 6]].
    - Update previousInterval to (6, 8).
- Remove (6, 8, 2, 0) from the queue. Priority queue: [(9, 12, 0, 1)].
  - Check if there is a gap between previousInterval and the current interval (9, 12):
    - Gap found between (8, 9). Add this interval to result: result = [[4, 6], [8, 9]].
    - Update previousInterval to (9, 12).
- Remove (9, 12, 0, 1) from the queue. Priority queue is now empty.
Return result: [[4, 6], [8, 9]].

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

The above algorithm’s time complexity is $O(N*logK)$ , where ‘N’ is the total number of intervals, and ‘K’ is the total number of employees. This is because we are iterating through the intervals only once (which will take O(N)), and every time we process an interval, we remove (and can insert) one interval in the Min Heap, (which will take $O(logK)$ ). At any time, the heap will not have more than ‘K’ elements.

Space Complexity

The space complexity of the above algorithm will be $O(K)$ as at any time, the heap will not have more than $K$ elements.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible