LeetCode 759 - Employee Free Time

Difficulty: 🔴 Hard
Topics: Array, Sweep Line, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to determine common free time intervals for a group of employees based on their schedules. Each employee has a list of non-overlapping intervals representing times when they are busy. Our goal is to find periods where all employees are simultaneously free, excluding any intervals of zero length. The schedules are guaranteed to be sorted for each employee, and intervals are strictly within [0, 10^8].

The input schedule is a list of lists of Interval objects. For example, schedule[i] represents employee i's working times, and schedule[i][j] is an interval [start, end] for that employee. The output is a list of Interval objects representing the free time where no employee is busy. Intervals extending to infinity (like [-inf, start] or [end, inf]) are ignored.

Key points include that intervals do not overlap within the same employee, but they can overlap between employees. Edge cases to note include schedules where all employees are always busy without any gaps, schedules with only one employee, and intervals that touch but do not overlap (like [1,3] and [3,5]).

Approaches

Brute Force

The brute-force approach would involve iterating through all possible time points from the minimum start to the maximum end across all employees and checking which times are free for all. This would require creating a timeline and marking each employee’s busy times, then finding continuous free segments. While correct, this is highly inefficient because the time range can go up to 10^8, making a linear scan impractical.

Optimal Approach

The key observation is that we only care about start and end points of intervals. By flattening all employee schedules into a single list of intervals and sorting by start time, we can merge overlapping intervals to get the union of all busy times. Once merged, the gaps between these merged intervals represent common free time. This approach leverages the fact that employees’ schedules are already non-overlapping internally, so merging is straightforward and efficient.

We can also use a priority queue (min-heap) approach, which merges intervals in sorted order across multiple employees without needing to flatten the entire list first. Both methods effectively reduce the problem to merging intervals and finding gaps.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(Range) ~ O(10^8)	O(Range)	Marking timeline of all times, impractical
Optimal (Sort & Merge)	O(N log N), N = total intervals	O(N)	Flatten and merge intervals, then find gaps
Optimal (Heap)	O(N log k), N = total intervals, k = #employees	O(k)	Use heap to merge sorted intervals across employees

Algorithm Walkthrough

Flatten schedules: Iterate through each employee’s list of intervals and collect all intervals into a single list. This converts a list of lists into a single list for easier processing.
Sort intervals: Sort all intervals by start time. Sorting ensures that when we merge intervals, we can do it in a single pass.
Merge overlapping intervals: Initialize a variable prev with the first interval. Iterate through the sorted list. If the current interval starts after prev.end, there is a free interval from prev.end to current.start. Update prev to be the current interval’s end if it extends beyond prev.end.
Collect gaps: Each time we detect that the current interval starts after prev.end, append a new Interval(prev.end, current.start) to the result list. This represents common free time.
Return result: After iterating through all intervals, return the list of free intervals.

Why it works: By merging all busy intervals across employees, we obtain a continuous timeline of busy periods. The gaps between these merged intervals are precisely the times when no employee is working, satisfying the requirement of common free time. Sorting ensures correct order, and merging ensures overlapping busy intervals do not create false gaps.

Python Solution

"""
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        # Flatten all intervals from all employees
        all_intervals = [iv for emp in schedule for iv in emp]
        
        # Sort intervals by start time
        all_intervals.sort(key=lambda x: x.start)
        
        # Merge intervals and find gaps
        free_times = []
        prev = all_intervals[0]
        
        for curr in all_intervals[1:]:
            if curr.start > prev.end:
                # Gap found
                free_times.append(Interval(prev.end, curr.start))
                prev = curr
            else:
                # Merge overlapping intervals
                prev.end = max(prev.end, curr.end)
        
        return free_times

Explanation: First, we flatten all intervals for easier processing. Sorting ensures we handle intervals in chronological order. The merging step tracks the end of the previous interval and finds gaps for free time. Overlaps are merged to avoid false gaps. Finally, we return all detected free intervals.

Go Solution

/**
 * Definition for an Interval.
 * type Interval struct {
 *     Start int
 *     End   int
 * }
 */

import "sort"

func employeeFreeTime(schedule [][]*Interval) []*Interval {
    // Flatten all intervals
    allIntervals := []*Interval{}
    for _, emp := range schedule {
        allIntervals = append(allIntervals, emp...)
    }
    
    // Sort intervals by start time
    sort.Slice(allIntervals, func(i, j int) bool {
        return allIntervals[i].Start < allIntervals[j].Start
    })
    
    freeTimes := []*Interval{}
    prev := allIntervals[0]
    
    for _, curr := range allIntervals[1:] {
        if curr.Start > prev.End {
            // Gap found
            freeTimes = append(freeTimes, &Interval{Start: prev.End, End: curr.Start})
            prev = curr
        } else {
            // Merge overlapping intervals
            if curr.End > prev.End {
                prev.End = curr.End
            }
        }
    }
    
    return freeTimes
}

Go-specific notes: We handle slices with append and sorting with sort.Slice. Merging updates the prev reference in-place. Go requires careful pointer management for intervals, unlike Python where object references are naturally handled.

Worked Examples

Example 1

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

Flattened intervals: [1,2],[5,6],[1,3],[4,10]

Sorted intervals: [1,2],[1,3],[4,10],[5,6] → merged by start-end:

Merge [1,2] and [1,3] → [1,3]
Gap [3,4] → free time
Merge [4,10] with [5,6] → [4,10]

Output: [[3,4]]

Example 2

Input: [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]

Flattened: [1,3],[6,7],[2,4],[2,5],[9,12]

Sorted: [1,3],[2,4],[2,5],[6,7],[9,12]

Merge steps:

Merge [1,3],[2,4],[2,5] → [1,5]
Gap [5,6] → free time
Merge [6,7] → [6,7]
Gap [7,9] → free time
Merge [9,12] → [9,12]

Output: [[5,6],[7,9]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N log N)	Sorting all intervals dominates, N = total intervals
Space	O(N)	Flattened list of intervals plus result list

Flattening requires O(N) space, and sorting requires O(N log N). The merging loop is O(N), so the overall complexity is dominated by sorting.

Test Cases

# Provided examples
assert [ (iv.start, iv.end) for iv in Solution().employeeFreeTime([[Interval(1,2),Interval(5,6)],[Interval(1,3)],[Interval(4,10)]])] == [(3,4)]  # Example 1
assert [ (iv.start, iv.end) for iv in Solution().employeeFreeTime([[Interval(1,3),Interval(6,7)],[Interval(2,4)],[Interval(2,5),Interval(9,12)]])] == [(5,6),(7,9)]  # Example 2

# Edge cases
assert Solution().employeeFreeTime([[Interval(1,3)]]) == []  # Single employee, no free time
assert [ (iv.start, iv.end) for iv in Solution().employeeFreeTime([[Interval(1,2)],[Interval(3,4)]])] == [(2,3)]  #