We iterate over each employee's schedule and extract start and end times as events, marking starts with +1 and ends with -1.
💡 Separating intervals into start and end events allows us to process all interval boundaries uniformly.
Line:for emp in schedule:
for interval in emp:
events.append((interval[0], 1)) # start event
events.append((interval[1], -1)) # end event
💡 This step transforms nested intervals into a flat list of events, preparing for sorting and sweeping.
setup
Sort events by time and type
We sort the events by their time; if two events have the same time, end events (-1) come before start events (+1).
💡 Sorting ensures we process events in chronological order and handle interval ends before starts at the same time.
Line:events.sort(key=lambda x: (x[0], x[1]))
💡 This ordering prevents counting intervals as active before they actually start when times tie.
setup
Initialize sweep line variables
We initialize 'active' to 0 to track how many intervals are currently active, and 'prev' to None to store the previous event time.
💡 Tracking active intervals helps us know when all employees are free (active == 0).
Line:free_times = []
active = 0
prev = None
💡 These variables set the stage for the sweep line to detect free time gaps.
traverse
Process first event (start at 1)
We process the first event at time 1, which is a start event (+1). Since active is 0 and prev is None, no free time is recorded. We increment active to 1 and set prev to 1.
💡 The first event starts an interval, so no free time can exist before it.
Line:for time, e_type in events:
if active == 0 and prev is not None and prev < time:
free_times.append([prev, time])
active += e_type
prev = time
💡 Active intervals increase, indicating employees are busy starting now.
traverse
Process second event (start at 1)
We process the second event, also a start at time 1. Active is currently 1, so no free time is recorded. We increment active to 2 and update prev to 1.
💡 Multiple intervals can start at the same time, increasing active count.
Line:active += e_type
prev = time
💡 Active count reflects overlapping intervals starting simultaneously.
traverse
Process third event (end at 2)
We process an end event at time 2. Active is 2, so no free time is recorded. We decrement active to 1 and update prev to 2.
💡 An interval ends, reducing the number of active intervals.
Line:active += e_type
prev = time
💡 Active count decreases as intervals close, tracking ongoing coverage.
traverse
Process fourth event (end at 3)
We process an end event at time 3. Active is 1, so no free time is recorded. We decrement active to 0 and update prev to 3.
💡 Active reaching zero means no intervals are currently covering the timeline.
Line:active += e_type
prev = time
💡 Active zero signals a potential start of free time after this event.
traverse
Process fifth event (start at 4)
We process a start event at time 4. Since active is 0 and prev is 3, and 3 < 4, we record free time [3,4]. Then we increment active to 1 and update prev to 4.
💡 When active is zero, the gap between prev and current time is free time for all employees.
Line:if active == 0 and prev is not None and prev < time:
free_times.append([prev, time])
active += e_type
prev = time
💡 This step reveals how the algorithm detects free time intervals between busy periods.
traverse
Process sixth event (start at 5)
We process a start event at time 5. Active is 1, so no free time is recorded. We increment active to 2 and update prev to 5.
💡 Intervals starting again increase active count, ending free time periods.
Line:active += e_type
prev = time
💡 Active count rising means employees are busy again.
traverse
Process seventh event (end at 6)
We process an end event at time 6. Active is 2, so no free time is recorded. We decrement active to 1 and update prev to 6.
💡 Intervals ending reduce active count but still indicate busy time.
Line:active += e_type
prev = time
💡 Active count tracks ongoing coverage accurately.
traverse
Process eighth event (end at 10)
We process the last event, an end at time 10. Active is 1, so no free time is recorded. We decrement active to 0 and update prev to 10.
💡 Active reaching zero at the end means all intervals have closed.
Line:active += e_type
prev = time
💡 The timeline is fully processed with no further free time after last interval.
reconstruct
Return the free time intervals
After processing all events, we return the list of free time intervals found, which is [[3,4]].
💡 The final answer is the list of gaps where no employee is working.
Line:return free_times
💡 The algorithm successfully identifies the free time between merged intervals.
from typing import List
def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
events = [] # STEP 1
for emp in schedule: # STEP 1
for interval in emp: # STEP 1
events.append((interval[0], 1)) # start event # STEP 1
events.append((interval[1], -1)) # end event # STEP 1
events.sort(key=lambda x: (x[0], x[1])) # STEP 2
free_times = [] # STEP 3
active = 0 # STEP 3
prev = None # STEP 3
for time, e_type in events: # STEP 4 to 11
if active == 0 and prev is not None and prev < time: # STEP 8
free_times.append([prev, time]) # STEP 8
active += e_type # STEP 4 to 11
prev = time # STEP 4 to 11
return free_times # STEP 12
# Driver code
if __name__ == '__main__':
schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
print(employeeFreeTime(schedule))
📊
Employee Free Time - Watch the Algorithm Execute, Step by Step
Watching each event processed and how the active interval count changes reveals exactly when free time intervals appear, making the logic crystal clear.
Step 1/12
·Active fill★Answer cell
record
(1,1)
0
(2,-1)
1
(5,1)
2
(6,-1)
3
(1,1)
4
(3,-1)
5
(4,1)
6
(10,-1)
7
Result: []
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
i
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
(1,1)
0
i
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
(1,1)
0
(1,1)
1
i
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
i
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: []
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
i
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
i
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
i
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
move_right
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
i
(10,-1)
7
Result: [[3,4]]
record
(1,1)
0
(1,1)
1
(2,-1)
2
(3,-1)
3
(4,1)
4
(5,1)
5
(6,-1)
6
(10,-1)
7
Result: [[3,4]]
Key Takeaways
✓ Transforming intervals into start and end events allows a uniform sweep line approach.
This insight is hard to see from code alone because the flattening and sorting steps are subtle but crucial.
✓ Sorting events with end events before start events at the same time prevents counting intervals as active prematurely.
This ordering detail is easy to overlook but essential for correct active interval tracking.
✓ When the active count drops to zero, the gap between previous and current event times is free time.
Watching the active count change step-by-step reveals exactly when free time intervals appear.
Practice
(1/5)
1. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?
easy
A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.
B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.
C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.
D. Use dynamic programming to store and compute overlapping intervals between the two lists.
Solution
Step 1: Understand problem constraints
Both lists are sorted and non-overlapping internally, so a linear scan is possible.
Step 2: Identify the optimal approach
Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.
Final Answer:
Option B -> Option B
Quick Check:
Two pointers avoid unnecessary comparisons and achieve linear time [OK]
Hint: Two pointers exploit sorted order for linear time [OK]
Common Mistakes:
Assuming brute force is acceptable
Thinking sorting combined lists is needed
Misapplying DP to interval intersection
2. You are given a list of intervals and need to remove all intervals that are covered by another interval. Which approach guarantees an optimal solution with O(n log n) time complexity and O(1) extra space besides the input?
easy
A. Use a brute force nested loop to check coverage between every pair of intervals.
B. Sort intervals by start ascending and end descending, then scan once to count uncovered intervals.
C. Use dynamic programming to find the maximum set of non-covered intervals.
D. Sort intervals by end ascending and greedily pick intervals that do not overlap.
Solution
Step 1: Understand sorting criteria
Sorting intervals by start ascending and end descending ensures intervals with the same start are ordered from longest to shortest, so coverage can be detected in one pass.
Step 2: Single pass coverage check
By scanning intervals in sorted order and tracking the maximum end seen, we can count intervals that are not covered by any previous interval.
Final Answer:
Option B -> Option B
Quick Check:
Sorting by start ascending and end descending enables O(n log n) sorting plus O(n) scanning [OK]
Hint: Sort by start asc, end desc, then scan once [OK]
Common Mistakes:
Sorting only by start ascending misses coverage when starts equal
Using nested loops causes TLE on large inputs
3. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.
medium
A. Line adding interval end event should use end + 1 instead of end.
B. Sorting key should sort points before interval starts.
C. Active count should be incremented after processing points, not before.
D. Result array initialization size is incorrect.
Solution
Step 1: Identify event creation for interval ends
Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.
Step 2: Understand effect on counting
Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.
Final Answer:
Option A -> Option A
Quick Check:
Changing to end + 1 fixes counting for points at interval ends [OK]
Hint: Interval end event must be at end+1 to include points at end [OK]
Common Mistakes:
Using end instead of end+1
Misordering events
Incorrect active count update
4. The following code attempts to determine if a person can attend all meetings. Identify the line containing the subtle bug that causes incorrect results for intervals that just touch (e.g., [1,5] and [5,10]).
from typing import List
def can_attend_meetings(intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
end = float('-inf')
for interval in intervals:
if interval[0] <= end:
return False
end = interval[1]
return True
medium
A. Line 6: if interval[0] <= end:
B. Line 3: intervals.sort(key=lambda x: x[0])
C. Line 5: for interval in intervals:
D. Line 7: end = interval[1]
Solution
Step 1: Understand the overlap condition
Meetings that just touch (e.g., end=5 and start=5) should not be considered overlapping.
Step 2: Identify the bug
The condition uses <= which incorrectly treats touching intervals as overlapping. It should use < instead.
Final Answer:
Option A -> Option A
Quick Check:
Changing <= to < fixes false positives on touching intervals [OK]
Hint: Overlap check must use <, not <= [OK]
Common Mistakes:
Using <= causes false overlap detection on touching intervals
5. What is the time complexity of the sweep line algorithm for finding the minimum number of platforms required given n trains, and why?
medium
A. O(n log n) due to sorting arrivals and departures separately and merging them.
B. O(n^2) because each event is compared with all others to count overlaps.
C. O(n) because we only iterate through arrivals and departures once.
D. O(n log n) because events are sorted and then processed in a single pass.
Solution
Step 1: Identify sorting as the main cost
We create 2n events and sort them by time, which takes O(n log n).
Step 2: Single pass processing after sorting
After sorting, we iterate through events once, O(n), updating counts.
Final Answer:
Option A -> Option A
Quick Check:
Sorting dominates, linear sweep after [OK]
Hint: Sorting events dominates time complexity [OK]
Common Mistakes:
Assuming O(n) because of single pass ignoring sorting
Confusing nested loops brute force with sweep line
Thinking sorting arrivals and departures separately is enough
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.