Employee Free Time

hard intervals heap sorting

Problem

Given schedules of employees as lists of disjoint intervals, return the list of finite intervals representing common free time across all employees, sorted by start.

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

Output[[3,4]]

All employees are free between time 3 and 4.

input

def employeeFreeTime(schedule):
    ivs = sorted([iv for emp in schedule for iv in emp], key=lambda x: x[0])
    res = []
    end = ivs[0][1]
    for s, e in ivs[1:]:
        if s > end:
            res.append([end, s])
        end = max(end, e)
    return res

function employeeFreeTime(schedule) {
  const ivs = schedule.flat().sort((a,b) => a[0]-b[0]);
  const res = [];
  let end = ivs[0][1];
  for (let i = 1; i < ivs.length; i++) {
    const [s, e] = ivs[i];
    if (s > end) res.push([end, s]);
    end = Math.max(end, e);
  }
  return res;
}

List<int[]> employeeFreeTime(List<List<int[]>> schedule) {
    List<int[]> ivs = new ArrayList<>();
    for (var emp : schedule) ivs.addAll(emp);
    ivs.sort((a,b) -> a[0]-b[0]);
    List<int[]> res = new ArrayList<>();
    int end = ivs.get(0)[1];
    for (int i = 1; i < ivs.size(); i++) {
        int[] iv = ivs.get(i);
        if (iv[0] > end) res.add(new int[]{end, iv[0]});
        end = Math.max(end, iv[1]);
    }
    return res;
}

vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
    vector<vector<int>> ivs;
    for (auto& emp : schedule) for (auto& iv : emp) ivs.push_back(iv);
    sort(ivs.begin(), ivs.end(), [](auto& a, auto& b){ return a[0] < b[0]; });
    vector<vector<int>> res;
    int end = ivs[0][1];
    for (int i = 1; i < (int)ivs.size(); i++) {
        if (ivs[i][0] > end) res.push_back({end, ivs[i][0]});
        end = max(end, ivs[i][1]);
    }
    return res;
}

Explanation

Common free time is simply the gaps left over after every employee's busy interval is laid on one timeline. So we throw all the busy intervals into a single list and sort them by start.

Then we sweep left to right tracking end, the farthest point covered so far. For each next interval [s, e], if its start s is greater than end, nobody is busy between end and s, so [end, s] is a shared free slot.

Whether or not we found a gap, we extend coverage with end = max(end, e). Using the running max (not just e) matters because a long interval can swallow several shorter ones.

Example: flattening gives [1,2], [1,3], [4,10], [5,6]. After [1,3] the coverage ends at 3, and the next interval starts at 4, so [3,4] is the only free time, giving [[3,4]].

Sorting once and sweeping once is all it takes, since the gaps can only appear between consecutive intervals on the merged timeline.

Time: O(n log n) Space: O(n)