Employee Free Time

Problem

For ‘K’ employees, we are given a list of intervals representing the working hours of each employee. Our goal is to find out if there is a free interval that is common to all employees. You can assume that each list of employee working hours is sorted on the start time.

Examples

Example 1

Input: Employee Working Hours=[[[1,3], [5,6]], [[2,3], [6,8]]]
Output: [3,5]
Explanation: Both the employees are free between [3,5].

Example 2

Input: Employee Working Hours=[[[1,3], [9,12]], [[2,4]], [[6,8]]]
Output: [4,6], [8,9]
Explanation: All employees are free between [4,6] and [8,9].

Example 3

Input: Employee Working Hours=[[[1,3]], [[2,4]], [[3,5], [7,9]]]
Output: [5,7]
Explanation: All employees are free between [5,7].

Solution

Method 1

Intuition

We want to find gaps between all employees' working intervals. Since each employee's intervals are sorted, we can efficiently merge all intervals and look for gaps. Using a min-heap allows us to always process the earliest interval next, making it easy to find free time between intervals.

Approach

1. Insert the first interval of each employee into a min-heap (ordered by start time).
2. Track the latest end time seen so far.
3. Pop the smallest start-time interval from the heap, and if its start is after the latest end, record the gap as free time.
4. Update the latest end time.
5. If the employee has more intervals, push the next one into the heap.
6. Repeat until all intervals are processed.

Code

C++

class Solution {
public:
    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
        using T = tuple<int, int, int, int>; // start, end, emp, idx
        priority_queue<T, vector<T>, greater<T>> pq;
        for (int i = 0; i < schedule.size(); ++i)
            pq.emplace(schedule[i][0][0], schedule[i][0][1], i, 0);
        int prevEnd = get<1>(pq.top());
        vector<vector<int>> res;
        while (!pq.empty()) {
            auto [start, end, emp, idx] = pq.top(); pq.pop();
            if (start > prevEnd)
                res.push_back({prevEnd, start});
            prevEnd = max(prevEnd, end);
            if (idx + 1 < schedule[emp].size())
                pq.emplace(schedule[emp][idx+1][0], schedule[emp][idx+1][1], emp, idx+1);
        }
        return res;
    }
};

Go

type Interval struct{ Start, End int }
type Item struct{ Start, End, Emp, Idx int }
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Start < h[j].Start }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func employeeFreeTime(schedule [][][]int) [][]int {
    h := &MinHeap{}
    heap.Init(h)
    for emp, intervals := range schedule {
        heap.Push(h, Item{intervals[0][0], intervals[0][1], emp, 0})
    }
    prevEnd := (*h)[0].End
    res := [][]int{}
    for h.Len() > 0 {
        cur := heap.Pop(h).(Item)
        if cur.Start > prevEnd {
            res = append(res, []int{prevEnd, cur.Start})
        }
        if cur.End > prevEnd {
            prevEnd = cur.End
        }
        if cur.Idx+1 < len(schedule[cur.Emp]) {
            next := schedule[cur.Emp][cur.Idx+1]
            heap.Push(h, Item{next[0], next[1], cur.Emp, cur.Idx+1})
        }
    }
    return res
}

Java

class Solution {
    public List<List<Integer>> employeeFreeTime(List<List<Interval>> schedule) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < schedule.size(); i++) {
            pq.offer(new int[]{schedule.get(i).get(0).start, schedule.get(i).get(0).end, i, 0});
        }
        int prevEnd = pq.peek()[1];
        List<List<Integer>> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (cur[0] > prevEnd) res.add(Arrays.asList(prevEnd, cur[0]));
            prevEnd = Math.max(prevEnd, cur[1]);
            int emp = cur[2], idx = cur[3];
            if (idx + 1 < schedule.get(emp).size()) {
                Interval next = schedule.get(emp).get(idx + 1);
                pq.offer(new int[]{next.start, next.end, emp, idx + 1});
            }
        }
        return res;
    }
    static class Interval {
        int start, end;
        Interval(int s, int e) { start = s; end = e; }
    }
}

Kotlin

class Solution {
    fun employeeFreeTime(schedule: List<List<Interval>>): List<List<Int>> {
        data class Item(val start: Int, val end: Int, val emp: Int, val idx: Int)
        val pq = PriorityQueue<Item>(compareBy { it.start })
        for ((emp, intervals) in schedule.withIndex()) {
            pq.add(Item(intervals[0].start, intervals[0].end, emp, 0))
        }
        var prevEnd = pq.peek().end
        val res = mutableListOf<List<Int>>()
        while (pq.isNotEmpty()) {
            val cur = pq.poll()
            if (cur.start > prevEnd) res.add(listOf(prevEnd, cur.start))
            prevEnd = maxOf(prevEnd, cur.end)
            if (cur.idx + 1 < schedule[cur.emp].size) {
                val next = schedule[cur.emp][cur.idx + 1]
                pq.add(Item(next.start, next.end, cur.emp, cur.idx + 1))
            }
        }
        return res
    }
    data class Interval(val start: Int, val end: Int)
}

Python

import heapq
class Solution:
    def employeeFreeTime(self, schedule: List[List[Interval]]) -> List[List[int]]:
        heap = []
        for emp, intervals in enumerate(schedule):
            heapq.heappush(heap, (intervals[0].start, intervals[0].end, emp, 0))
        prev_end = heap[0][1]
        res = []
        while heap:
            start, end, emp, idx = heapq.heappop(heap)
            if start > prev_end:
                res.append([prev_end, start])
            prev_end = max(prev_end, end)
            if idx + 1 < len(schedule[emp]):
                next_interval = schedule[emp][idx + 1]
                heapq.heappush(heap, (next_interval.start, next_interval.end, emp, idx + 1))
        return res
class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end

Rust

use std::collections::BinaryHeap;
use std::cmp::Reverse;
#[derive(Eq, PartialEq)]
struct Item { start: i32, end: i32, emp: usize, idx: usize }
impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.start.cmp(&self.start)
    }
}
impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
fn employee_free_time(schedule: Vec<Vec<(i32, i32)>>) -> Vec<(i32, i32)> {
    let mut heap = BinaryHeap::new();
    for (emp, intervals) in schedule.iter().enumerate() {
        let (start, end) = intervals[0];
        heap.push(Reverse(Item { start, end, emp, idx: 0 }));
    }
    let mut prev_end = if let Some(Reverse(item)) = heap.peek() { item.end } else { 0 };
    let mut res = vec![];
    while let Some(Reverse(cur)) = heap.pop() {
        if cur.start > prev_end {
            res.push((prev_end, cur.start));
        }
        prev_end = prev_end.max(cur.end);
        if cur.idx + 1 < schedule[cur.emp].len() {
            let (start, end) = schedule[cur.emp][cur.idx + 1];
            heap.push(Reverse(Item { start, end, emp: cur.emp, idx: cur.idx + 1 }));
        }
    }
    res
}

TypeScript

class Interval {
    constructor(public start: number, public end: number) {}
}
class Solution {
    employeeFreeTime(schedule: Interval[][]): number[][] {
        type Item = [number, number, number, number]; // start, end, emp, idx
        const heap: Item[] = [];
        for (let emp = 0; emp < schedule.length; emp++) {
            heap.push([schedule[emp][0].start, schedule[emp][0].end, emp, 0]);
        }
        heap.sort((a, b) => a[0] - b[0]);
        let prevEnd = heap[0][1];
        const res: number[][] = [];
        while (heap.length) {
            const [start, end, emp, idx] = heap.shift()!;
            if (start > prevEnd) res.push([prevEnd, start]);
            prevEnd = Math.max(prevEnd, end);
            if (idx + 1 < schedule[emp].length) {
                const next = schedule[emp][idx + 1];
                heap.push([next.start, next.end, emp, idx + 1]);
                heap.sort((a, b) => a[0] - b[0]);
            }
        }
        return res;
    }
}

Complexity

• Time Complexity: O(N * log K), where N is the total number of intervals and K is the number of employees. Each interval is processed once, and each heap operation is O(log K).
• Space Complexity: O(K), since the heap contains at most K elements at any time.