Why this fails:

1. Coordinate Range: The time coordinates can be very large (up to $10^8$). allocating an array of this size will result in a Memory Limit Exceeded or Time Limit Exceeded error.
2. Sparse Data: Most of the timeline might be empty or filled with long continuous blocks. Iterating through every single time unit is inefficient compared to processing the interval endpoints directly.

Core Insight for Employee Free Time

The core insight for solving LeetCode 759 is that the distinction between different employees does not matter. Whether Employee A works from 1:00 to 3:00 and Employee B works from 2:00 to 4:00, or if a single employee works both shifts, the "busy" time is the continuous block from 1:00 to 4:00.

Therefore, we can flatten the input. Instead of a list of lists, we treat the input as a single large collection of working intervals.

Once flattened, the problem transforms into finding gaps in a set of intervals. To do this efficiently, we must process time chronologically. By sorting all intervals by their start time, we enforce an invariant: as we iterate, we never encounter an interval that starts earlier than the one we just processed.

With a sorted list, we can maintain a running max_end variable representing the end of the current continuous block of work. When we encounter a new interval:

1. If the new interval starts after our current max_end, a gap exists. The free time is [max_end, current_interval.start].
2. If the new interval starts before or exactly at max_end, it overlaps (or touches) the current block. We merge them by updating max_end to be the maximum of the current max_end and the new interval's end.

Visual Description: Imagine drawing all intervals on a horizontal timeline. Sorting aligns them left-to-right based on when they begin. We place a pointer at the end of the first interval. We look at the next interval in the sorted list. If there is empty space between our pointer and the start of this next interval, that space is "Free Time." If the next interval overlaps with our pointer, we extend our pointer to the end of that interval (if it extends further). We repeat this sweep until the end.

Execution Flow

Consider the input: schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]

1. Flatten: [[1,2], [5,6], [1,3], [4,10]]
2. Sort: [[1,2], [1,3], [4,10], [5,6]] (Sorted by start time)
3. Initialize:
   • max_end = 2 (from [1,2])
   • result = []
4. Iteration:
   • Current Interval: [1,3]
     • Is 1 > 2? No.
     • Overlap exists. Update max_end = max(2, 3) = 3.
   • Current Interval: [4,10]
     • Is 4 > 3? Yes.
     • Gap Found: Free time is [3, 4]. Add to result.
     • Update max_end = 10.
   • Current Interval: [5,6]
     • Is 5 > 10? No.
     • Overlap exists. Update max_end = max(10, 6) = 10.
5. Final Result: [[3, 4]].

Proof of Correctness

The algorithm relies on the Greedy Choice Property. By sorting intervals by start time, we ensure that we process potential overlaps in chronological order. When we track max_end, we are effectively maintaining the "frontier" of the current continuous working block.

If the next earliest starting interval begins after max_end, it is impossible for any other interval to cover that gap, because all subsequent intervals also have start times greater than or equal to the current one (due to sorting). Thus, the gap [max_end, current.start] is definitively free time. This guarantees that the algorithm finds all global free time intervals correctly.

Reference Implementation

C++ Solution for LeetCode 759

cpp
/*
// Definition for an Interval.
class Interval {
public:
    int start;
    int end;

    Interval() {}

    Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        vector<Interval> allIntervals;
        
        // Flatten the schedule into a single list
        for (const auto& employee : schedule) {
            for (const auto& interval : employee) {
                allIntervals.push_back(interval);
            }
        }
        
        // Sort by start time
        sort(allIntervals.begin(), allIntervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });
        
        vector<Interval> result;
        if (allIntervals.empty()) return result;
        
        // Initialize max_end with the first interval's end
        int max_end = allIntervals[0].end;
        
        // Iterate through sorted intervals
        for (size_t i = 1; i < allIntervals.size(); ++i) {
            if (allIntervals[i].start > max_end) {
                // Gap detected
                result.push_back(Interval(max_end, allIntervals[i].start));
                max_end = allIntervals[i].end;
            } else {
                // Overlap or touching, extend the current block
                max_end = max(max_end, allIntervals[i].end);
            }
        }
        
        return result;
    }
};

Java Solution for LeetCode 759

java
/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> allIntervals = new ArrayList<>();
        
        // Flatten the schedule
        for (List<Interval> employee : schedule) {
            allIntervals.addAll(employee);
        }
        
        // Sort by start time
        Collections.sort(allIntervals, (a, b) -> a.start - b.start);
        
        List<Interval> result = new ArrayList<>();
        if (allIntervals.isEmpty()) return result;
        
        // Initialize tracking variable
        int maxEnd = allIntervals.get(0).end;
        
        // Iterate through sorted intervals
        for (int i = 1; i < allIntervals.size(); i++) {
            Interval current = allIntervals.get(i);
            
            if (current.start > maxEnd) {
                // Found a free time gap
                result.add(new Interval(maxEnd, current.start));
                maxEnd = current.end;
            } else {
                // Merge intervals
                maxEnd = Math.max(maxEnd, current.end);
            }
        }
        
        return result;
    }
}

Python Solution for LeetCode 759

python
"""
# 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 the list of lists into a single list
        all_intervals = []
        for emp in schedule:
            for interval in emp:
                all_intervals.append(interval)
        
        # Sort intervals by start time
        all_intervals.sort(key=lambda x: x.start)
        
        result = []
        if not all_intervals:
            return result
            
        # Initialize the end of the first working block
        max_end = all_intervals[0].end
        
        # Iterate through the rest of the intervals
        for i in range(1, len(all_intervals)):
            current = all_intervals[i]
            
            if current.start > max_end:
                # Gap found between max_end and current.start
                result.append(Interval(max_end, current.start))
                max_end = current.end
            else:
                # Overlap: extend the current working block
                max_end = max(max_end, current.end)
                
        return result