Editorial
Core insight
Employee Free Time · Greedy Patterns
Core Insight for Employee Free Time
The fundamental inefficiency of the brute force solution is evaluating time units where nothing changes. The state of the system (how many employees are working) only changes at the exact moment an interval begins or ends.
By extracting all start and end times from every interval and treating them as independent "events", we can sort these events chronologically. As we process these events in order, we maintain a running counter of active employees. A start event increments the counter, and an end event decrements it. The core invariant is simple: whenever the active employee counter drops to zero, a period of common free time begins. The free time ends exactly at the timestamp of the next event, which will inevitably be a start event that increments the counter back to one.
Visual Description: Imagine a 1D horizontal timeline. Vertical lines are dropped at every start time and end time. An algorithm moves a vertical "sweep line" from left to right across this timeline. As the sweep line crosses a start event, an internal counter increments. As it crosses an end event, the counter decrements. The algorithm only records a gap when it traverses the space between an end event that dropped the counter to zero and the subsequent start event that raises it back to one.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 759: Employee Free Time Solution & Explanation
Problem Overview
TL;DR: Flatten all employee schedules into discrete start and end events, sort them chronologically, and sweep across the timeline to find gaps where zero employees are actively working.
In LeetCode 759, you are given a nested list of intervals representing the work schedules of multiple employees. Your objective is to find all finite intervals during which no employee is working. The result must be a sorted list of continuous free time blocks, bounded by the earliest start time and the latest end time across all given schedules. Finding the optimal Employee Free Time is a popular interview question because it rigorously tests a candidate's ability to process and merge overlapping intervals efficiently.
Brute Force Approach for Employee Free Time
A naive approach to solving this problem involves checking every single unit of time (e.g., minute by minute or hour by hour) to see if any employee is working.
function findFreeTime(schedule):
min_time = find_minimum_start_time(schedule)
max_time = find_maximum_end_time(schedule)
free_intervals = []
current_free_start = -1
for time from min_time to max_time:
is_working = false
for employee in schedule:
if employee_is_working_at(employee, time):
is_working = true
break
if not is_working and current_free_start == -1:
current_free_start = time
else if is_working and current_free_start != -1:
free_intervals.add([current_free_start, time])
current_free_start = -1
return free_intervalsComplexity and Failure Analysis: The time complexity of this brute force approach is , where is the total range of time (maximum end time minus minimum start time) and is the total number of employees.
This approach fails catastrophically due to Time Limit Exceeded (TLE) constraints. Interval values in scheduling problems can easily span into the hundreds of millions. Iterating over continuous time units rather than discrete events wastes immense computational resources on periods where no state changes occur.
Algorithm Strategy: Greedy Line Sweep
To implement the optimal solution for interviews using the Line Sweep pattern, we completely discard the concept of individual employees.
Instead, we flatten the 2D schedule into a 1D list of events. Each event requires two pieces of data: the timestamp, and the type of event (+1 for an interval start, -1 for an interval end).
Once the events are collected, we sort them. The primary sorting key is the timestamp (ascending order). The secondary sorting key is crucial: if two events share the same timestamp, we must process start events (+1) before end events (-1). This prevents our active worker counter from momentarily dipping to zero when one interval ends exactly as another begins, which would incorrectly register a zero-length free time block.
Finally, we iterate through the sorted events, maintaining the active worker count and tracking the timestamp where the count last reached zero.
Execution Flow
- Initialize an empty list
events. - Iterate through every interval in the given
schedule. For each interval[start, end], append(start, 1)and(end, -1)toevents. - Sort
eventsprimarily by timestamp in ascending order. If timestamps are identical, sort by the event type in descending order so that1(start) precedes-1(end). - Initialize
active_workers = 0,prev_time = -1, and an empty listfree_time. - Iterate through each
eventin the sortedeventslist:- If
active_workers == 0andprev_time != -1and the current event's time is strictly greater thanprev_time, we have found a valid free block. Append[prev_time, current_time]tofree_time. - Add the current event's type (+1 or -1) to
active_workers. - If
active_workersbecomes0after the update, updateprev_timeto the current event's time.
- If
- Return the
free_timelist.
Proof of Correctness
The algorithm's correctness relies on the Line Sweep invariant: at any point during the sweep, the active_workers variable perfectly represents the number of overlapping intervals at the current timestamp.
Because we sort start events before end events at the same timestamp, contiguous work blocks (e.g., [1, 3] and [3, 5]) are seamlessly merged. The counter correctly transitions from 1 to 2, then back to 1, never hitting 0 at timestamp 3. Therefore, a free time block is only recorded when there is a genuine, finite gap between the absolute end of all overlapping work intervals and the start of the next one. Bounding is naturally handled because the counter starts at 0 before the first event and ends at 0 after the last event, preventing infinite intervals from being recorded.
Pattern Reuse Notes
The Line Sweep subpattern is a highly versatile tool in Greedy Patterns. The exact same logic of extracting events, sorting them, and tracking active overlaps is utilized in:
In Interval List Intersections, instead of looking for periods where the active counter drops to zero, you apply the exact same sweep line and look for periods where the active counter reaches two (indicating an intersection). Mastering this event-based state tracking provides a reliable template for almost any interval manipulation problem.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 759
1/*
2// Definition for an Interval.
3class Interval {
4public:
5 int start;
6 int end;
7 Interval() {}
8 Interval(int _start, int _end) {
9 start = _start;
10 end = _end;
11 }
12};
13*/
14
15class Solution {
16public:
17 vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
18 vector<pair<int, int>> events;
19
20 // Extract all start and end events
21 for (const auto& emp : schedule) {
22 for (const auto& iv : emp) {
23 events.push_back({iv.start, 1});
24 events.push_back({iv.end, -1});
25 }
26 }
27
28 // Sort events: primary by time (asc), secondary by delta (desc)
29 sort(events.begin(), events.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
30 if (a.first != b.first) return a.first < b.first;
31 return a.second > b.second; // 1 (start) comes before -1 (end)
32 });
33
34 vector<Interval> freeTime;
35 int activeWorkers = 0;
36 int prevTime = -1;
37
38 // Sweep line across sorted events
39 for (const auto& event : events) {
40 int time = event.first;
41 int delta = event.second;
42
43 // If no workers were active and time has advanced, record the gap
44 if (activeWorkers == 0 && prevTime != -1 && time > prevTime) {
45 freeTime.push_back(Interval(prevTime, time));
46 }
47
48 activeWorkers += delta;
49
50 // Mark the start of a potential free period
51 if (activeWorkers == 0) {
52 prevTime = time;
53 }
54 }
55
56 return freeTime;
57 }
58};Java Solution for LeetCode 759
1/*
2// Definition for an Interval.
3class Interval {
4 public int start;
5 public int end;
6 public Interval() {}
7 public Interval(int _start, int _end) {
8 start = _start;
9 end = _end;
10 }
11};
12*/
13
14class Solution {
15 public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
16 List<int[]> events = new ArrayList<>();
17
18 // Extract all start and end events
19 for (List<Interval> emp : schedule) {
20 for (Interval iv : emp) {
21 events.add(new int[]{iv.start, 1});
22 events.add(new int[]{iv.end, -1});
23 }
24 }
25
26 // Sort events: primary by time (asc), secondary by delta (desc)
27 events.sort((a, b) -> {
28 if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
29 return Integer.compare(b[1], a[1]); // 1 comes before -1
30 });
31
32 List<Interval> freeTime = new ArrayList<>();
33 int activeWorkers = 0;
34 int prevTime = -1;
35
36 // Sweep line across sorted events
37 for (int[] event : events) {
38 int time = event[0];
39 int delta = event[1];
40
41 // If no workers were active and time has advanced, record the gap
42 if (activeWorkers == 0 && prevTime != -1 && time > prevTime) {
43 freeTime.add(new Interval(prevTime, time));
44 }
45
46 activeWorkers += delta;
47
48 // Mark the start of a potential free period
49 if (activeWorkers == 0) {
50 prevTime = time;
51 }
52 }
53
54 return freeTime;
55 }
56}Python Solution for LeetCode 759
1"""
2# Definition for an Interval.
3class Interval:
4 def __init__(self, start: int = None, end: int = None):
5 self.start = start
6 self.end = end
7"""
8
9class Solution:
10 def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
11 events = []
12
13 # Extract all start and end events
14 for emp in schedule:
15 for iv in emp:
16 events.append((iv.start, 1))
17 events.append((iv.end, -1))
18
19 # Sort events: primary by time (asc), secondary by delta (desc)
20 # Using -x[1] ensures 1 sorts before -1 when times are equal
21 events.sort(key=lambda x: (x[0], -x[1]))
22
23 free_time = []
24 active_workers = 0
25 prev_time = -1
26
27 # Sweep line across sorted events
28 for time, delta in events:
29 # If no workers were active and time has advanced, record the gap
30 if active_workers == 0 and prev_time != -1 and time > prev_time:
31 free_time.append(Interval(prev_time, time))
32
33 active_workers += delta
34
35 # Mark the start of a potential free period
36 if active_workers == 0:
37 prev_time = time
38
39 return free_time