Employee Free Time LeetCode Solution

Problem Statement

Employee Free Time LeetCode Solution – 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 the 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

Test Case 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.

Approach:

Let’s solve the problem step by step. First, let’s assume that each employee only has one interval of working time. We can sort the intervals by the starting time in ascending order. Then we iterate the intervals. While iterating, we keep track of the previous latest ending time. If for any interval, its starting time is larger than the previous latest ending time, then we have found a free time interval for all employees and we add it to the result.

Now let’s consider the case when each employee may have more than one interval. We first consider the first interval of all employees. We can use a priority queue to store and sort these intervals. We sort the intervals by their starting time. We also keep track of the latest ending time latestEnd we have traversed so far. Each time, we poll an interval from the queue. This interval is the one with the smallest starting time in the PQ. If the current interval’s starting time is larger than latestEnd, then we have found a free time interval and we add the corresponding free interval to the result. After this, if the employee of the current interval still has other intervals left, we add it to the PQ. We repeat the process until the PQ is empty.

Code for Employee Free Time

Java Program

/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        // We store the pointers of the intervals instead of intervals themselves
        // int[]{i, j} where i represents the ith employee and
        // j represents the jth interval of the ith employee
        PriorityQueue<int[]> pq = new PriorityQueue<>(schedule.size(),
            (a, b) -> (schedule.get(a[0]).get(a[1]).start
                     - schedule.get(b[0]).get(b[1]).start));
        
        // Initialize with the first interval of all employees
        for (int i = 0; i < schedule.size(); i += 1) {
            pq.offer(new int[]{i, 0});
        }
        
        // Initialize the latest ending time
        int latestEnd = schedule.get(pq.peek()[0]).get(0).end;
        
        List<Interval> res = new LinkedList<>();
        while (!pq.isEmpty()) {
            int[] indices = pq.poll();
            List<Interval> employee = schedule.get(indices[0]);
            Interval cur = employee.get(indices[1]);
            
            if (cur.start > latestEnd) {
                res.add(new Interval(latestEnd, cur.start));
            }
            
            if (indices[1] < employee.size() - 1) {
                pq.offer(new int[]{indices[0], indices[1] + 1});
            }
            latestEnd = Math.max(latestEnd, cur.end);
        }
        return res;
    }
}

C++ Program

/*
// Definition for an Interval.
class Interval {
public:
    int start;
    int end;

    Interval() {}

    Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        const int _inf = -1, inf = 1e9;
    auto getFreeTime = [&](vector<Interval> &inv) {
      int prevEn = -1;
      vector<Interval> freeTime;
      for (Interval &i: inv) {
        freeTime.push_back(Interval(prevEn, i.start));
        prevEn = i.end;
      }
      freeTime.push_back(Interval(prevEn, inf));
      return freeTime;
    };
    auto getCommon = [](vector<Interval> &a, vector<Interval> &b) {
      int n = a.size(), m = b.size(), i = 0, j = 0;
      vector<Interval> common;
      while (i < n && j < m) {
        int st = max(a[i].start, b[j].start), en = min(a[i].end, b[j].end);
        if (en > st) {
          common.push_back(Interval(st, en));
        }
        if (a[i].end < b[j].end) i++;
        else j++;
      }
      return common;
    }; 
    for (vector<Interval> &inv: schedule) {
      inv = getFreeTime(inv);
    }
    vector<Interval> common = {Interval(_inf, inf)};
    for (vector<Interval> &inv: schedule) {
      common = getCommon(common, inv);
    }
    vector<Interval> ans;
    for (Interval &i: common) {
      if (i.start == _inf || i.end == inf) continue;
      ans.push_back(i);
    }
    return ans;
    }
};

Complexity Analysis for Employee Free Time LeetCode Solution

Time complexity: O(N·logK) where N is the total number of intervals and K is the number of employees. We initialize the PQ with K intervals where K is the number of employees. At each loop, we poll one element from the queue, and we may or may not add at most one element to the queue. Therefore the PQ’s size is no bigger than K. And we will repeat this for N intervals.
Space complexity: O(N)