Employee Free Time

It is very famous problem on LeetCode, which took a while for me to understand and solve, and It’s asked by Fang Company many times.

Problem Description

Given a list of schedule of employees, which represent 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 interval in the form of [x, y], the object inside are intervals not lists or arrays. For example schedule[0][0].start. = 1, schedule[0][0].end = 3 , and schedule[0][0][0] is not defined). Also, we would not include intervals like [5,5] in our answer as the have 0 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]]

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

Approach

Here, I have used heap approach for this problem.

What is Heap?

A heap (also referred to as a priority queue) is a specialized binary tree. Specifically, it is a complete binary tree. The keys must satisfy the heap property — the key at each node is at least as great as the keys stored at its children.

A max-heap can be implemented as an array; the children of the node at index i are at indices 2i +1and 2i + 2. The array representation for the max-heap is (561, 314, 401, 28,156,359, 271,11,3). A max-heap supports O(log n) insertions, O(1) time lookup for the max element, and O(log n) deletion of the max element. The extract-max operation is defined to delete and return the maximum element. Searching for arbitrary keys has O(n) time complexity.

The min-heap is a completely symmetric version of the data structure and supports O(1) time lookups for the minimum element

Where we can use Heap?

when we all care about the largest and smallest elements, and we do not need fast lookup, delete, or search operations for arbitrary elements.

Algorithm

we will assume that each employee list is individually sorted!

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.

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

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
        List<Interval> result = new ArrayList();
        PriorityQueue<EmployeeInterval> heap = new PriorityQueue<EmployeeInterval>((a, b) ->
            avails.get(a.employeeIndex).get(a.intervalIndex).start -
            avails.get(b.employeeIndex).get(b.intervalIndex).start);
        int ei = 0, time = Integer.MAX_VALUE;
    // we will keep track of the latest time that we don't know of a job overlapping that  time.
     for (List<Interval> employee: avails) {
            heap.offer(new EmployeeInterval(ei++, 0));
            time = Math.min(time, employee.get(0).start);
        }
      while (!heap.isEmpty()) {
            EmployeeInterval job = heap.poll();
            Interval iv = avails.get(job.employeeIndex).get(job.intervalIndex);
            if (time < iv.start)
                result.add(new Interval(time, iv.start));
            time = Math.max(time, iv.end);
            if (++job.intervalIndex < avails.get(job.employeeIndex).size())
                heap.offer(job);
        }
        return result;
    }
}
class EmployeeInterval{
    
    // index of the list containing working hours of this employee    
    // index of the interval in the employee list 
    
    int employeeIndex, intervalIndex; 
    
    EmployeeInterval(int e, int i) {
        employeeIndex = e;
        intervalIndex = i;
    }
}