AlgoMaster Logo

Employee Free Time

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have multiple employees, each with their own set of working intervals. We need to find the time slots where no employee is working, which are the gaps between the merged union of all working intervals.

Consider a single timeline with every employee's working hours marked on it. Wherever no interval covers the timeline, that uncovered stretch is free time for everyone. Those uncovered gaps are the answer.

Which employee an interval belongs to does not matter. We can collect all intervals from all employees, merge the overlapping ones, and the gaps between consecutive merged intervals are the common free time.

Key Constraints:

  • 1 <= schedule.length, schedule[i].length <= 50. At most 50 employees, each with at most 50 intervals, so the total number of intervals N is at most 2,500. The input is small enough that even an O(N^2) approach would pass, but the natural solutions here are O(N log N) or better.
  • 0 <= schedule[i][j].start < schedule[i][j].end <= 10^8. Values reach 10^8, which fits comfortably in a 32-bit signed integer (max about 2.1 x 10^9), so subtracting two start times in a comparator cannot overflow. The time range itself is large, so iterating over individual time units is out of the question.
  • Each employee's intervals are non-overlapping and sorted by start time. This lets us merge the K employee lists in order without re-sorting everything (Approach 2).

Approach 1: Flatten, Sort, and Find Gaps

Intuition

Collect every working interval from every employee into one list, sort it by start time, then scan through it to find the gaps.

While scanning, track the farthest endpoint seen so far in prevEnd. If the next interval starts after prevEnd, the stretch between prevEnd and that start is uncovered, so it is free time. If the next interval starts at or before prevEnd, it overlaps the covered region, and we extend prevEnd to whichever endpoint is larger.

This is the merge-intervals pattern, except instead of outputting the merged blocks we output the gaps between them.

Algorithm

  1. Collect all intervals from all employees into a single list.
  2. Sort the list by start time.
  3. Initialize prevEnd to the end of the first interval.
  4. Iterate through the sorted intervals starting from the second one.
  5. If the current interval's start is greater than prevEnd, add the gap [prevEnd, current.start] to the result.
  6. Update prevEnd to be the maximum of prevEnd and the current interval's end.
  7. Return the result list.

Visualization and Code

Loading animation...

Flattening and re-sorting discards the fact that each employee's intervals already arrive sorted. With K sorted lists, the next approach merges them in global order without a full sort.

Approach 2: Min-Heap (Merge K Sorted Lists)

Intuition

Each employee's intervals are already sorted by start time, so we have K sorted lists of intervals. Instead of dumping them into one array and sorting, a min-heap pulls the next interval in global sorted order. Seed the heap with the first interval of each employee, then repeatedly extract the interval with the smallest start time, check it for a gap, and push that employee's next interval into the heap.

This holds at most K intervals in memory at once rather than all N, which is the win when K is much smaller than N.

Algorithm

  1. Create a min-heap. For each employee, push their first interval along with the employee index and interval index.
  2. Pull the first element from the heap to initialize prevEnd.
  3. Push that employee's next interval (if any) into the heap.
  4. While the heap is not empty:
    • Extract the interval with the smallest start time.
    • If its start is greater than prevEnd, add the gap [prevEnd, start] to the result.
    • Update prevEnd to max(prevEnd, current.end).
    • Push the next interval from the same employee into the heap (if any).
  5. Return the result.

Visualization and Code

Loading animation...

The next approach decomposes each interval into separate start and end events and sweeps through the timeline, which counts how many employees overlap at any moment rather than merging whole intervals.

Approach 3: Line Sweep (Event-Based)

Intuition

Break each interval into two events: a "start working" event and a "stop working" event. Sort all events by time, then sweep through them tracking how many employees are currently working.

Whenever the active count drops to zero and later rises again, the span between those two moments is free for everyone.

This is the line sweep technique, which applies to interval problems generally, from meeting rooms to the skyline problem.

One ordering detail matters: when a start event and an end event share the same time, process the end event first. Otherwise an interval ending at t and another starting at t would briefly register a false drop to zero at t, producing a spurious zero-length gap. Sorting by (time, type) with type = -1 for end and +1 for start places ends before starts at equal times, so the count never dips between two intervals that touch.

Algorithm

  1. For each interval [start, end], create two events: (start, +1) for "someone starts working" and (end, -1) for "someone stops working".
  2. Sort events by time. If two events have the same time, process end events (-1) before start events (+1).
  3. Sweep through events, maintaining a running count of active workers.
  4. Whenever the count drops to 0, record the current time as a potential gap start.
  5. When the count rises above 0 after being 0, the gap from the recorded start to the current time is a free interval (if it has positive length).

Visualization and Code

Loading animation...