Employee Free Time

▶

Steps

setup

Collect start and end events

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.

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. You are given a list of intervals, each with a start and end time. For each interval, you want to find the interval with the smallest start time that is greater than or equal to the end time of the current interval. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use two max-heaps: one for interval starts and one for interval ends, to efficiently find the next interval.

B. Use a greedy algorithm that picks the earliest finishing interval first.

C. Sort intervals by start time and use dynamic programming to find the next interval.

D. Use a brute force nested loop to compare each interval with every other interval.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding, for each interval, the next interval with the smallest start time ≥ current interval's end time.

2. Step 2: Evaluate approaches

   Brute force (nested loops) is correct but inefficient (O(n²)). Sorting + binary search is efficient but requires extra steps. The two max-heaps approach efficiently tracks max starts and ends to find next intervals in O(n log n) time, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps approach matches the problem's need for efficient next interval lookup [OK]

Hint: Two heaps efficiently track max starts and ends [OK]

Common Mistakes:

• Assuming greedy earliest finish works
• Using DP unnecessarily
• Brute force accepted as optimal

2. What is the time complexity of the optimal balanced two heaps approach with indexed removal (using a balanced BST or multiset) for computing the median of every sliding window of size k in an array of length n?

medium

A. O(n log n)

B. O(n log k)

C. O(n k)

D. O(n k log k)

Solution

1. Step 1: Identify operations per window slide

   Each slide requires removing one element and inserting another into balanced BST/multiset, each O(log k).

2. Step 2: Calculate total complexity

   There are n-k+1 windows, so total complexity is O(n log k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Balanced BST operations cost O(log k) per insertion/removal [OK]

Hint: Each insertion/removal costs O(log k), done n times [OK]

Common Mistakes:

• Confusing n and k in complexity
• Assuming sorting each window (O(k log k)) per slide
• Ignoring log factor in balanced BST operations

3. Consider the following buggy code snippet for the two heaps approach to find next intervals. Which line contains the subtle bug that causes incorrect results on some inputs?

import heapq

def find_next_intervals(intervals):
    n = len(intervals)
    result = [-1] * n
    max_start_heap = []
    max_end_heap = []

    for i, (start, end) in enumerate(intervals):
        heapq.heappush(max_start_heap, (start, i))  # Line 9
        heapq.heappush(max_end_heap, (-end, i))

    while max_end_heap:
        end, end_idx = heapq.heappop(max_end_heap)
        end = -end

        if not max_start_heap or -max_start_heap[0][0] < end:
            continue

        candidates = []
        while max_start_heap and -max_start_heap[0][0] >= end:
            start, start_idx = heapq.heappop(max_start_heap)
            candidates.append((start, start_idx))

        min_start, min_idx = max(candidates)
        result[end_idx] = min_idx

        for c in candidates:
            if c != (min_start, min_idx):
                heapq.heappush(max_start_heap, c)

    return result

medium

A. Line 12: Pushing intervals into max_end_heap with negative end times.

B. Line 9: Using a min-heap push with (start, i) instead of max-heap with (-start, i).

C. Line 18: Checking if max_start_heap is empty or top start < end incorrectly.

D. Line 26: Pushing back unused candidates into max_start_heap.

Solution

1. Step 1: Identify heap usage

   max_start_heap must be a max-heap by pushing (-start, i) to pop intervals with largest start first.

2. Step 2: Analyze Line 9

   Line 9 pushes (start, i) without negation, making it a min-heap, breaking the logic that relies on max-heap ordering.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using min-heap here causes incorrect candidate selection [OK]

Hint: Max-heap requires negation; missing negation breaks logic [OK]

Common Mistakes:

• Forgetting to negate start for max-heap
• Misusing min-heap for max-heap logic
• Incorrect candidate selection due to heap order

4. The following code attempts to rearrange a string so that the same characters are at least k distance apart. Identify the line containing the subtle bug that can cause invalid output or failure.

medium

A. Line: heapq.heapify(max_heap) # heapify should be replaced with sort

B. Line: if k == 0: return s # should handle k=1 differently

C. Line: queue.append((char, count)) # decrement count missing

D. Line: if front_count < 0: heapq.heappush(max_heap, (front_count, front_char)) # should check for <= 0

Solution

1. Step 1: Identify decrement of count

   The algorithm must decrement the count of the character after using it, i.e., count + 1 since counts are negative.

2. Step 2: Locate missing decrement

   In the buggy line, count is appended without incrementing, so the character count never decreases, causing infinite loops or invalid results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct decrement is critical to track usage [OK]

Hint: Check if character count is updated after usage [OK]

Common Mistakes:

• Forgetting to decrement count after popping from heap
• Misusing queue length to enforce k-distance
• Incorrect heap operations or conditions

5. Suppose the problem is modified so that each element in the array can be used multiple times (reused) to form a multiset, and you want to minimize the deviation of the multiset's elements after allowed operations. Which modification to the optimal max-heap approach is necessary to handle this variant correctly?

hard

A. Switch to a min-heap and double even numbers instead of halving max

B. No change needed; the original max-heap approach works as is

C. Track counts of each element and update min_val accordingly when reusing elements

D. Use dynamic programming to consider all reuse combinations explicitly

Solution

1. Step 1: Understand reuse impact on deviation calculation

   Reusing elements means multiple copies affect min and max values, so counts must be tracked.

2. Step 2: Modify heap approach to track counts

   Track counts of elements in heap and update min_val carefully when elements are reused or halved to maintain correct deviation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Counting duplicates ensures correct min and max tracking with reuse [OK]

Hint: Reusing elements requires tracking counts to update min and max correctly [OK]

Common Mistakes:

• Assuming original approach works without tracking duplicates
• Switching heap type incorrectly
• Trying brute force reuse without pruning