Employee Free Time

Patrick Leaton
Published: July 14, 2021, 10:14 a.m.
Problem Description

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

 

The description was taken from https://leetcode.com/problems/employee-free-time/.

Problem Solution

#O(N(Log N)) Time, O(N) Space
class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        output, heap = [], []
        
        for employee in schedule:
            for interval in employee:
                heapq.heappush(heap, (interval.start, interval.end))
        
        _, max_end = heapq.heappop(heap)
 
        while heap:
            start, end = heapq.heappop(heap)
            if start > max_end:
                output.append(Interval(max_end, start))
            max_end = max(max_end, end)
        return output

Problem Explanation

This question is an interval question.  Interval questions typically require greedy solutions.  Greedy solutions typically consist of sorting the input and focusing on the most costly tasks or the cheapest tasks to conserve the most resources.

This question is a bit different than the traditional greedy solution, but it still follows the same principle.  What we can do is sort the input intervals and calculate the maximum end-time from each iteration.  That maximum end-time will be our most costly task.  

By doing this, we will be able to compare the greatest end-time on one hand, with each current start-time on the other.  If we have a start time that comes after the greatest end-time, that will mean we have a block of time where there is no overlap, in which case there is free time for the employees.  

We can append each occurrence of this event to the output and we are done!

This part of the function specifies that it will require an array of objects from the Interval class and will be returning an array of objects from the Interval class.

 def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':

 

Let's start by initializing our heap and output lists. 

        output, heap = [], []

 

We could choose just to use a list that we'd append each interval to and sort it afterward, but let's just use a heap for that since it is sorted each time we append to it.

Let's iterate through each Interval object within the schedule list, and let's iterate through each start-time and end-time from each interval object.

For each interval object, we are going to append its start time and end-time to the heap.  Since the start time is appended first in the tuple, the heap will sort these intervals based on their start times.

        for employee in schedule:
            for interval in employee:
                heapq.heappush(heap, (interval.start, interval.end))

 

Next, we will start traversing our intervals, but first, let's initialize our max_end variable that will track the greatest end-time so far as mentioned previously.

        _, max_end = heapq.heappop(heap)

 

Now let's traverse the rest of the intervals starting with the second since we just popped off the first.

Within each iteration, we will pop a start-time and an end-time off of our heap.

        while heap:
            start, end = heapq.heappop(heap)

 

If the current interval's start time is greater than the maximum end-time, we have a vacant block of time between these two times.

If that is the case, we will utilize these two times to make a new instance of the Interval class, since that is what the function is expecting, and we will append that instance to the output.

            if start > max_end:
                output.append(Interval(max_end, start))

 

Next, we will check if the current end time is greater than the maximum end time we have saved, if it is then we will make it the new maximum end time.

            max_end = max(max_end, end)

 

Once we have popped everything off the heap, we will have traversed all of our intervals and checked for any vacant blocks of time, which we appended to the output.

        return output