Space

Open

From Fieldwork

Scales

759. Employee Free Time

leetcodehardarraysortingheappriority-queueline-sweep

v1

This approach is O(N \log N) because we re-sort everything. It's concise and works well for typical memory limits.

However, if the input schedule was extremely large (like a data stream) or didn't fit in memory, We would optimize this to O(N log K) using a Min-Heap to merge the sorted lists effectively.

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        # 1. Flatten the list of lists
        all_intervals = []
        for emp in schedule:
            for interval in emp:
                all_intervals.append(interval)
        
        # 2. Sort by start time (destroys the pre-sorted property, but it's fast)
        all_intervals.sort(key=lambda x: x.start)
        
        result = []
        prev_end = all_intervals[0].end
        
        # 3. Standard Sweep Line
        for i in range(1, len(all_intervals)):
            curr = all_intervals[i]
            
            if curr.start > prev_end:
                # Found a gap
                result.append(Interval(prev_end, curr.start))
                prev_end = curr.end
            else:
                # Overlap: extend our known busy time
                prev_end = max(prev_end, curr.end)
                
        return result

v2

This approach is basically Merge K Sorted Lists (a classic hard pattern).

The Concept: "Streaming" the Intervals

Instead of dumping all intervals into a bucket and sorting them (which destroys the pre-sorted property given to us), we use a Min-Heap to keep track of the "next earliest available interval" among all employees.

So like basically, rather than doing a "lets collect everything and mash it into one blob and sort it" we simply... go through the existing semi-sorted structure and continue to enforce the sortedness as we go along and collect everything.

The Heap size will never exceed K (the number of employees).

The Algorithm

Initialize: Add the first interval of every employee into a Min-Heap.
Heap Tuple: (start_time, employee_index, interval_index)
Track: Pop the smallest start time from the heap. This is our current interval.
Process: Compare with prev_end (just like the previous solution).
Refill: Once we process an interval from Employee X, grab Employee X's next interval and push it into the heap.

Approach 1 (Flatten & Sort): "I don't trust the input. I will dump everything on the floor, mix it up, and re-organize it from scratch."

Approach 2 (Heap): "I trust the input is locally sorted. I will just look at the front of each line and pick the winner."

The Visual: The "Funnel"

Think of the Min-Heap as a funnel. We pour K different sorted streams into the top, and the heap guarantees that what drops out of the bottom is always the single smallest element, one by one.

We are "enforcing sortedness" by maintaining an invariant: The heap always holds the next available candidate from every employee. It never holds more than one interval per employee, so it stays small and fast.

Bonus: The "Iterator" Pattern

This is essentially the Iterator Pattern.

We are creating a "Super Iterator" that wraps around K smaller iterators.

Functions like Python's heapq.merge or Java's Guava Iterators.mergeSorted do exactly this under the hood.

Knowing this problem well demonstrates that we understand how to build tools that process data lazily (only fetching the next item when asked), which is critical for massive distributed systems (like MapReduce).

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        min_heap = []
        
        # 1. Initialize Heap with the first interval of each employee
        # Heap Tuple: (start_time, employee_idx, interval_idx)
        for employee_idx, emp_schedule in enumerate(schedule):
            if emp_schedule:
                # We store the start time for sorting, and indices to find the next one
                start_time = emp_schedule[0].start
                heapq.heappush(min_heap, (start_time, employee_idx, 0))
        
        result = []
        
        # Initialize prev_end. We need to peek at the first real interval.
        if not min_heap:
            return []
            
        # Peek at the first interval (employee_idx, 0)
        # We don't pop yet, just need to set the initial 'busy' boundary
        first_emp_idx = min_heap[0][1]
        prev_end = schedule[first_emp_idx][0].end
        
        # 2. Process the Heap
        while min_heap:
            # Pop the earliest starting interval
            start, emp_idx, interval_idx = heapq.heappop(min_heap)
            
            # Access the actual object using our indices
            curr_interval = schedule[emp_idx][interval_idx]
            
            # Check for Gap
            if start > prev_end:
                result.append(Interval(prev_end, start))
                prev_end = curr_interval.end
            else:
                # Extend the busy block
                prev_end = max(prev_end, curr_interval.end)
            
            # 3. Refill the heap with THIS employee's next interval
            next_interval_idx = interval_idx + 1
            if next_interval_idx < len(schedule[emp_idx]):
                next_interval = schedule[emp_idx][next_interval_idx]
                heapq.heappush(min_heap, (next_interval.start, emp_idx, next_interval_idx))
                
        return result

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeNov 29, 2025