# Employee Free Time LeetCode Solution

Difficulty Level Hard
Frequently asked in Airbnb Amazon Apple Bloomberg ByteDance Coupang DoorDash Facebook Google Intuit Karat Microsoft Oracle Pinterest Quora Snapchat Uber Wayfair YahooViews 26

## 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.start = 1``schedule.end = 2`, and `schedule` is not defined).  Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

## Example

### Input:

schedule = [[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]

[[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).get(a).start
- schedule.get(b).get(b).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()).get(0).end;

while (!pq.isEmpty()) {
int[] indices = pq.poll();
List<Interval> employee = schedule.get(indices);
Interval cur = employee.get(indices);

if (cur.start > latestEnd) {
}

if (indices < employee.size() - 1) {
pq.offer(new int[]{indices, indices + 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)

Translate »