Solution: Employee Free Time

Statement

You’re given a list containing the schedules of multiple employees. Each person’s schedule is a list of non-overlapping intervals in a 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.

Note: The common free intervals are calculated between the earliest start time and the latest end time of all meetings across all employees.

Constraints:

• $1 \leq$ schedule.Length , schedule[i].Length $\leq 50$

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

Solution

The solution’s core revolves around merging overlapping intervals of employees and identifying the free time gaps between these merged intervals. Using a min-heap, we arrange the intervals based on when they start, sorting them according to their start times. When we pop an element from the min-heap, it guarantees that the earliest available interval is returned for processing. As intervals are popped from the min-heap, the algorithm attempts to merge them. If the currently popped interval’s start time exceeds the merged interval’s end time, a gap is identified, indicating a free period. After identifying each gap, the algorithm restarts the merging process to continue identifying additional periods of free time.

We use the following variables in our solution:

• previous: Stores the end time of the previously processed interval.
• i: Stores the employee’s index value.
• j: Stores the interval’s index of the employee, i.
• result: Stores the free time intervals.

The steps of the algorithm are given below :

• We store the start time of each employee’s first interval, along with its index value and a value of 0, in a min-heap.

• We set previous to the start time of the first interval present in a heap.

• Then, we iterate a loop until the heap is empty, and in each iteration, we do the following:

  • Pop an element from the min-heap and set i and j to the second and third values, respectively, from the popped value.
  • Select the interval from the input located at i,j.
  • If the selected interval’s start time is greater than previous, it means that the time from previous to the selected interval’s start time is free. So, add this interval to the result array.
  • Now, update the previous as $max(previous, end \; time \; of \; selected \;\; interval)$.
  • If the current employee has any other interval, push it into the heap.

• After all the iterations, when the heap becomes empty, return the result array.