Employee Free Time

This problem asks us to find the intervals of time when no employees are working, given a list of employees and their individual schedules.

Naive Solution

1. Collect all intervals: Iterate through each employee's schedule and add all the intervals to a single list.
2. Sort the intervals: Sort the combined list of intervals based on their start times.
3. Merge overlapping intervals: Iterate through the sorted intervals and merge any overlapping intervals.
4. Find the gaps: Iterate through the merged intervals. The gaps between the end of one interval and the start of the next are the free time intervals.

Edge Cases:

• Empty input: If the input list of employees is empty, there is no free time to calculate, return an empty list.
• No intervals: If all employees have empty schedules, there is infinite free time, return an empty list.
• Single Interval: if the schedule only contains a single interval, then the start of the free time is from negative infinity to start time of the interval and end of the interval to positive infinity.

Example:

Input: [[[1,2],[5,6]],[[1,3]],[[4,10]]]

1. Collect all intervals: [[1,2],[5,6],[1,3],[4,10]]
2. Sort intervals: [[1,2],[1,3],[4,10],[5,6]]
3. Merge intervals: [[1,3],[4,10]]
4. Find the gaps: [[3,4]]

Code (Python)

class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end


def employee_free_time_naive(schedule):
    intervals = []
    for employee in schedule:
        for interval in employee:
            intervals.append(interval)

    intervals.sort(key=lambda x: x.start)

    merged = []
    if intervals:
        merged.append(Interval(intervals[0].start, intervals[0].end))

    for interval in intervals[1:]:
        if interval.start <= merged[-1].end:
            merged[-1].end = max(merged[-1].end, interval.end)
        else:
            merged.append(Interval(interval.start, interval.end))

    free_time = []
    for i in range(len(merged) - 1):
        free_time.append(Interval(merged[i].end, merged[i+1].start))

    return free_time

Time Complexity

• O(N log N), where N is the total number of intervals. Sorting the intervals dominates the runtime.

Space Complexity

• O(N), where N is the total number of intervals. This is due to the space used to store the combined and merged intervals.

Optimal Solution

We can use a min-heap to efficiently find the free time. The min-heap will store intervals, prioritized by their start times.

1. Initialize the heap: Add the first interval from each employee's schedule to the min-heap.
2. Iterate and find gaps: While the heap is not empty, take the interval with the earliest start time.
   • If the current interval overlaps with the last processed interval, merge them.
   • If there's a gap between the current interval and the last processed interval, add the gap to the result.
   • Add the next interval from the employee who contributed the current interval to the heap.

Code (Python)

import heapq

class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end

    def __lt__(self, other):
        return self.start < other.start


def employee_free_time(schedule):
    min_heap = []
    for employee in schedule:
        if employee:
            heapq.heappush(min_heap, (employee[0].start, employee[0].end, schedule.index(employee), 0))

    free_time = []
    last_interval = Interval(float('-inf'), float('-inf'))

    while min_heap:
        start, end, emp_idx, interval_idx = heapq.heappop(min_heap)
        curr_interval = Interval(start, end)

        if curr_interval.start > last_interval.end:
            free_time.append(Interval(last_interval.end, curr_interval.start))

        last_interval = Interval(max(last_interval.start, curr_interval.start), max(last_interval.end, curr_interval.end))

        if interval_idx + 1 < len(schedule[emp_idx]):
            next_interval = schedule[emp_idx][interval_idx + 1]
            heapq.heappush(min_heap, (next_interval.start, next_interval.end, emp_idx, interval_idx + 1))

    return free_time

Time Complexity

• O(C log K), where C is the total number of intervals, and K is the number of employees. We perform log K operations for each interval during heap operations.

Space Complexity

• O(K), where K is the number of employees. This is the space used to store the intervals in the min-heap.