LeetCode 759: Employee Free Time

Problem Restatement

We are given the working schedules of several employees.

Each employee has a list of non-overlapping intervals, sorted by start time.

Each interval represents a time when that employee is busy.

We need to return all finite, positive-length intervals when every employee is free.

We do not include infinite intervals before the earliest busy time or after the latest busy time.

Input and Output

LeetCode uses an Interval class:

class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end

Example function shape:

def employeeFreeTime(schedule: list[list[Interval]]) -> list[Interval]:
    ...

Examples

Example 1:

schedule = [
    [Interval(1, 2), Interval(5, 6)],
    [Interval(1, 3)],
    [Interval(4, 10)],
]

Output:

[Interval(3, 4)]

The combined busy intervals are:

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

After merging busy time:

[1,3], [4,10]

The gap between them is:

[3,4]

That is the only finite common free time.

Example 2:

schedule = [
    [Interval(1, 3), Interval(6, 7)],
    [Interval(2, 4)],
    [Interval(2, 5), Interval(9, 12)],
]

Output:

[Interval(5, 6), Interval(7, 9)]

All employees are busy during the merged intervals:

[1,5], [6,7], [9,12]

The finite gaps are:

[5,6], [7,9]

First Thought: Check Every Time Unit

A direct idea is to mark every time unit as busy or free.

But interval endpoints can be as large as 10^8.

So marking every possible time value would be wasteful.

We only care about interval boundaries.

That means this is an interval merging problem.

Key Insight

All employees are free exactly when no employee is busy.

So instead of trying to compute free time directly, we first compute the union of all busy intervals.

Then common free time is simply the gaps between merged busy intervals.

For example:

Employee busy intervals:
[1,3], [6,7], [2,4], [2,5], [9,12]

Sorted:

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

Merged busy intervals:

[1,5], [6,7], [9,12]

Free intervals:

[5,6], [7,9]

Flatten All Schedules

The input is grouped by employee.

For merging, employee identity does not matter. Busy time from any employee blocks common free time.

So we flatten all intervals into one list:

intervals = []

for employee in schedule:
    for interval in employee:
        intervals.append(interval)

Then sort by start time:

intervals.sort(key=lambda interval: interval.start)

Merge Busy Intervals and Record Gaps

After sorting, scan from left to right.

Keep the farthest busy end seen so far:

prev_end

For each interval:

1. If interval.start > prev_end, there is a free gap:

[prev_end, interval.start]

2. Then update:

prev_end = max(prev_end, interval.end)

If interval.start <= prev_end, the interval overlaps or touches the current busy range, so there is no positive-length free time between them.

Algorithm

1. Flatten all employee intervals into one list.
2. Sort all intervals by start time.
3. Set prev_end to the end of the first interval.
4. For each later interval:
   1. If its start is greater than prev_end, append a free interval [prev_end, start].
   2. Update prev_end to the maximum of prev_end and the current interval end.
5. Return the free intervals.

Correctness

Every employee busy interval is added to the flattened list. Therefore, the flattened list contains exactly all times when at least one employee is busy.

After sorting by start time, scanning the intervals from left to right lets us maintain the merged busy region seen so far. The value prev_end is the right boundary of the current merged busy interval.

If the next interval starts at or before prev_end, it overlaps or touches the current busy region. There is no positive-length time gap where all employees are free, so the algorithm only extends prev_end if needed.

If the next interval starts after prev_end, then no busy interval covers the open time between prev_end and interval.start. Since all earlier busy intervals end no later than prev_end, and the next busy interval starts at interval.start, every employee is free during that finite positive-length interval. The algorithm appends exactly that gap.

Every finite common free interval must occur between two adjacent merged busy intervals. The algorithm records every such gap during the scan.

Therefore, the returned list contains exactly all finite positive-length intervals when all employees are free.

Complexity

Let N be the total number of intervals across all employees.

Implementation

"""
# 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]':
        intervals = []

        for employee in schedule:
            for interval in employee:
                intervals.append(interval)

        intervals.sort(key=lambda interval: interval.start)

        ans = []
        prev_end = intervals[0].end

        for interval in intervals[1:]:
            if interval.start > prev_end:
                ans.append(Interval(prev_end, interval.start))

            prev_end = max(prev_end, interval.end)

        return ans

Code Explanation

We first flatten the nested schedule:

intervals = []

for employee in schedule:
    for interval in employee:
        intervals.append(interval)

Once all busy intervals are in one list, we sort them:

intervals.sort(key=lambda interval: interval.start)

Now intervals are processed in chronological order.

We start the merged busy range with the first interval:

prev_end = intervals[0].end

Then we scan the remaining intervals:

for interval in intervals[1:]:

If the next busy interval starts after prev_end, there is a gap:

if interval.start > prev_end:
    ans.append(Interval(prev_end, interval.start))

The strict comparison matters.

If interval.start == prev_end, the gap has zero length, so it should not be included.

Then we update the right boundary of the current merged busy interval:

prev_end = max(prev_end, interval.end)

Finally, the answer contains all finite common free intervals.

Testing

For local testing, we can add a small helper to compare intervals.

class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end

def as_pairs(intervals: list[Interval]) -> list[list[int]]:
    return [[interval.start, interval.end] for interval in intervals]

def run_tests():
    s = Solution()

    schedule = [
        [Interval(1, 2), Interval(5, 6)],
        [Interval(1, 3)],
        [Interval(4, 10)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == [[3, 4]]

    schedule = [
        [Interval(1, 3), Interval(6, 7)],
        [Interval(2, 4)],
        [Interval(2, 5), Interval(9, 12)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == [[5, 6], [7, 9]]

    schedule = [
        [Interval(1, 5)],
        [Interval(2, 3)],
        [Interval(5, 8)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == []

    schedule = [
        [Interval(1, 2)],
        [Interval(4, 5)],
    ]
    assert as_pairs(s.employeeFreeTime(schedule)) == [[2, 4]]

    print("all tests passed")

run_tests()

Test meaning: