Employee Free Time

You are given the work calendars of several employees. schedule[i] is the list of busy intervals of employee i, each written as [start, end] with start < end. Within one employee's list the intervals are sorted by start time and never overlap.

Return every interval of time, of positive length, during which no employee is busy, as a list of [start, end] pairs sorted by start time. Only report finite gaps: the time before the earliest busy interval and after the latest one is ignored. Intervals that merely touch, such as [1, 5] and [5, 9], leave no gap between them. Return an empty list if there is no free time.

Example 1

Example 2

Example 3

Constraints

• 1 <= schedule.length <= 50
• 1 <= schedule[i].length <= 50
• 0 <= start < end <= 108
• Each employee's intervals are sorted and non-overlapping.

Pattern Path · Intervals & Greedy · problem 118 of 169

Start simple

Mark every time unit on a timeline array and collect the unmarked stretches: O(T + N) where T is the time range (up to 10⁸), which is far too large.

The key idea

A moment is free only if nobody is busy then, so the question is really about the union of all busy intervals. Ownership no longer matters: pool every interval into one list and sort it by start time.

Now sweep from left to right, keeping coveredUntil, the latest end time seen so far. Everything before coveredUntil (back to the first start) is covered by at least one interval. When the next interval starts at or before coveredUntil, it overlaps or touches the covered block, so we just extend coveredUntil if this interval ends later. When it starts strictly after coveredUntil, nothing covers the time in between, and because the list is sorted, no later interval can either. That gap [coveredUntil, start] is free time.

Tracking the maximum end (not just the previous interval's end) matters: a long meeting can swallow several shorter ones that come after it in the sorted order.

Sorting all N intervals costs O(N log N). Since each employee's list is already sorted, a min-heap that merges the k lists brings this down to O(N log k), which is the classic refinement.

Complexity

• Time: O(N log N) for N intervals in total (O(N log k) with a heap merge of k employees)
• Space: O(N)

Python

class Solution:
    def employeeFreeTime(self, schedule: List[List[List[int]]]) -> List[List[int]]:
        # Pool every busy interval, ordered by start time.
        busy = sorted(interval for person in schedule for interval in person)

        free = []
        covered_until = busy[0][1]  # everyone is accounted for up to this moment
        for start, end in busy[1:]:
            if start > covered_until:
                free.append([covered_until, start])  # nobody is busy in this gap
            covered_until = max(covered_until, end)
        return free

JavaScript

var employeeFreeTime = function(schedule) {
  // Pool every busy interval, ordered by start time.
  const busy = schedule.flat().sort((x, y) => x[0] - y[0]);

  const free = [];
  let coveredUntil = busy[0][1]; // everyone is accounted for up to this moment
  for (const [start, end] of busy.slice(1)) {
    if (start > coveredUntil) free.push([coveredUntil, start]); // nobody is busy in this gap
    coveredUntil = Math.max(coveredUntil, end);
  }
  return free;
};

What the interviewer is checking

The interviewer wants you to see that "free for everyone" means "gaps in the union", reducing the problem to a merge-intervals sweep, and then to improve it using the fact that each list is already sorted.

Mistakes to avoid

• Comparing with the previous interval's end instead of the running maximum end, which invents free time inside a long meeting.
• Reporting zero-length gaps when one interval ends exactly where the next starts.
• Including the unbounded time before the first meeting or after the last one.
• Finding the free time of each employee separately instead of the time free for all.

Follow-ups to expect

• Use the fact that each list is sorted. (Merge with a min-heap: O(N log k).)
• Find free slots of at least D minutes. (Filter gaps by length.)
• Find times when at least m people are free. (Sweep line over +1/−1 events.)

In real software

Calendar apps use this union-and-gaps sweep to suggest meeting times for a group, and schedulers use it to find windows where every node in a cluster is idle for maintenance.

Practice next