Employee Free Time (LeetCode 759)

The problem

You get each employee’s working schedule as a sorted list of non-overlapping busy intervals. Return the list of finite intervals during which all employees are free, in sorted order. Gaps of zero length (one interval ends exactly when another starts) do not count.

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

Someone is busy during 1–3 and someone during 4–10, so the only time nobody is working is 3 to 4. (LeetCode passes Interval objects; here each interval is a plain [start, end] list.)

How to think about it

Start with brute force. For every candidate gap, check every employee to see whether they are busy. Or mark every time unit on a timeline. Both depend on the size of the time range, not on the number of intervals.

The key insight: “everyone is free” means “nobody is busy”. You do not care whose interval is whose. Pool every busy interval from every employee into one list. The common free time is exactly the gaps in the union of those intervals, so this becomes Merge Intervals plus one extra step: record each gap.

You don’t even need to build the merged list. Sort the pooled intervals by start and keep only end, the furthest point covered so far. When the next interval starts after end, the stretch [end, s] is uncovered: that is free time. Then push end forward with max(end, e).

Which pattern is this? Merge intervals. The tell is “intervals from several sources” plus “time when none of them is active”. The optimal variant uses a min-heap to merge the already sorted lists in O(n log k), but a single sort is simpler and usually accepted.

Approach

1. Flatten all employees’ intervals into one list and sort it by start.
2. Set end to the first interval’s end.
3. For each remaining [s, e]: if s > end, append the gap [end, s].
4. Update end = max(end, e).
5. Return the gaps.

Solution

def employee_free_time(schedule):
    ints = sorted([iv for emp in schedule for iv in emp])   # pool everyone's busy time
    res = []; end = ints[0][1]                              # furthest busy point so far
    for s, e in ints[1:]:
        if s > end: res.append([end, s])                    # uncovered stretch: all free
        end = max(end, e)
    return res
# employee_free_time([[[1,2],[5,6]],[[1,3]],[[4,10]]]) -> [[3,4]]

Dry run

Pooled and sorted: [[1, 2], [1, 3], [4, 10], [5, 6]]. Start with end = 2.

The answer is [[3, 4]].

Complexity

• Time: O(n log n), where n is the total number of intervals across all employees. The sort dominates.
• Space: O(n). The pooled list. A heap-based merge of the k sorted lists cuts this to O(k) extra and the time to O(n log k).

Edge cases and pitfalls

• No free time (everyone’s busy blocks chain together) returns [].
• Zero-length gaps are excluded. [[1, 3]] and [[3, 5]] give no free time because the test is s > end, not s >= end.
• Using e instead of max(end, e) breaks on nested intervals: [5, 6] inside [4, 10] would pull end back to 6, so a later interval starting at 8 would create a fake gap [6, 8].
• Time before the first interval and after the last is infinite, so it is never reported.
• Empty schedule would crash on ints[0]; LeetCode guarantees at least one interval.

Related problems

• Merge Intervals (LeetCode 56): the same sweep; this problem reports the gaps instead of the blocks.
• Interval List Intersections (LeetCode 986): combining two people’s interval lists, keeping common busy time.
• Merge k Sorted Lists (LeetCode 23): the heap technique behind the O(n log k) version.