## Problem

Problem ID: 759

Title: Employee Free Time

Difficulty: Hard

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

## Thoughts

For this problem, I utilised a technique used for Hackerrank’s Sprint Training question. The technique of storing the delta of intervals is very useful when you want to compute the number of overlapped intervals.

## Solution

General Idea: For each time (start/end) we will store the change in number of employees that will become busy. This will let us easily simulate moving through time and detecting any time intervals when none of the employees are busy (same as all employees free).

Data Structure: `map<int, int> busy_times` stores the `time`: delta in number of busy employee. We use ordered map so that we can iterate through the busy times in ascending order.

Algorithm:

• Populating `busy_times`
• As each interval is disjoint, this means that at `Interval.start` an employee becomes busy (`busy_times[Interval.start]++`) and at `Interval.end` an employee becomes free (`busy_times[Interval.end]--`).
• Getting free intervals:
• We will store the `prev_time` that stores the previous processed time and `busy_count` that tracks the number of busy employee
• Iterate through `busy_times`
• if the previous `busy_count=0`, it signifies that it is the end of a all employee free interval.
• Update the `prev_time` with the current time and `busy_count` with the current delta.

### Implementation

``````class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
map<int, int> busy_times;
int n = schedule.size();
for (const auto& emp_sch : schedule) {
for (const auto& interval : emp_sch) {
busy_times[interval.start]++;
busy_times[interval.end]--;
}
}

vector<Interval> ret;
int prev_time = -1;
int busy_count = -1;
for (const auto& [time, busy_delta] : busy_times) {
if (prev_time == -1) {
prev_time = time;
busy_count = busy_delta;
continue;
}
if (busy_count == 0) {
ret.emplace_back(prev_time, time);
}
busy_count += busy_delta;
prev_time = time;
}
return ret;
}
};
``````