LeetCode Solutions Blog

Employee Free Time

Number: 761

Difficulty: Hard

Paid? Yes

Problem Description

Given a list called schedule where each element represents an employee’s working hours as a list of non-overlapping, sorted intervals, return the list of finite intervals during which all employees are free (i.e. common free time with a positive length). Although the intervals are represented as [x, y], they are objects with properties start and end.

Key Insights

Flatten the schedule to combine all employees’ intervals.
Sort the flattened intervals by start time.
Merge overlapping intervals to form a consolidated view of busy times.
Identify gaps between merged intervals as the common free time.
Ensure free intervals have strictly positive length.

Space and Time Complexity

Time Complexity: O(N log N), where N is the total number of intervals (due to sorting).
Space Complexity: O(N), used for the flattened list and merged intervals.

Solution

The solution leverages interval merging. First, all intervals from every employee are collected and sorted by start time. By iterating through the sorted intervals, overlapping intervals are merged into one consolidated busy period. Finally, the gaps between consecutive merged intervals are identified as free periods available to all employees. This approach efficiently handles the intervals with a simple sort and a linear scan.

Code Solutions

# Class definition for Interval
class Interval:
    def __init__(self, start, end):
        self.start = start  # Start time of the interval
        self.end = end      # End time of the interval

def employeeFreeTime(schedule):
    # Flatten the schedule: extract all intervals from each employee
    allIntervals = []
    for employee in schedule:
        for interval in employee:
            allIntervals.append(interval)
    
    # Sort intervals by start time
    allIntervals.sort(key=lambda interval: interval.start)
    
    # Merge overlapping intervals
    merged = []
    prev = allIntervals[0]
    for interval in allIntervals[1:]:
        if interval.start <= prev.end:
            # Expand the previous interval if there is an overlap
            prev.end = max(prev.end, interval.end)
        else:
            merged.append(prev)
            prev = interval
    merged.append(prev)
    
    # Collect free times from the gaps between merged intervals
    freeTimes = []
    for i in range(1, len(merged)):
        # Only intervals with positive length are added
        if merged[i].start > merged[i-1].end:
            freeTimes.append(Interval(merged[i-1].end, merged[i].start))
    
    return freeTimes

# Example usage:
# schedule = [
#     [Interval(1,2), Interval(5,6)],
#     [Interval(1,3)],
#     [Interval(4,10)]
# ]
# freeTimes = employeeFreeTime(schedule)
# for interval in freeTimes:
#     print(f"[{interval.start}, {interval.end}]")