⚡Flashcard Drill➔
NeetCode #849LC-759HardIntervals
← Back to All Problems

#849 · #759 · Employee Free Time(员工空闲时间)

📌 Problem Statement & Constraints

You are given the working schedules of several employees as a list of lists of intervals schedule[i], each sorted and disjoint. Return the list of finite intervals representing the common free time for all employees, sorted by start. Constraints: 1 <= schedule.length <= 50, 0 <= schedule[i].length <= 50, 0 <= start < end <= 10^8.

💡 Core Algorithmic Approaches

  1. Collect every working interval from every employee into one list and sort by start.
  2. Merge them into a single set of busy blocks.
  3. The gaps between consecutive merged busy blocks are the times when everyone is free.
  4. Only finite gaps are reported, so the time before the first block and after the last are not included.

💻 Benchmark Python3 Implementation

class Solution:
    def employeeFreeTime(self, schedule):
        # each entry is an Interval with .start / .end attributes
        intervals = []
        for emp in schedule:
            for iv in emp:
                intervals.append((iv.start, iv.end))
        intervals.sort()
        res = []
        end = intervals[0][1]
        for s, e in intervals[1:]:
            if s > end:                         # a gap exists -> everyone is free
                res.append(Interval(end, s))
                end = e
            else:
                end = max(end, e)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(N log N) where N is the total number of intervals: the sort dominates.
💾 Space Complexity
O(N): the flattened interval list.

⚠️ Interview Pitfalls & Follow-ups

  • Emitting the gaps before the first and after the last block: those are unbounded or outside the schedule and must be excluded.
  • Using s >= end: touching intervals are not a free gap, so the test is strict s > end.
  • Merging only adjacent employees: the intervals must be merged globally, not per employee.
  • Assuming the merged result is sorted: sorting by start and merging preserves the order, so the gaps come out sorted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems