Task Scheduler II (Cooldown Tracking)

▶

Steps

setup

Initialize variables

Initialize an empty hash map 'next_available' to track the earliest day each task can be scheduled again. Set the current day counter to 1, representing the first day of scheduling.

💡 Setting up these variables is crucial because the hash map will enforce cooldown constraints, and the day counter tracks the schedule timeline.

Line:

next_available = {}
day = 1

💡 The algorithm starts with no cooldown restrictions and the first day ready to schedule tasks.

insert

Schedule task 1 on day 1

Process the first task (task 1). Since it has no cooldown restriction yet, schedule it on day 1. Update its next available day to day 5 (1 + 3 + 1).

💡 Scheduling the first occurrence of a task sets its cooldown window, preventing it from being scheduled again too soon.

Line:

t = 1
if t in next_available:
    day = max(day, next_available[t])
next_available[t] = day + space + 1
day += 1

💡 The cooldown for task 1 starts after day 1, blocking scheduling until day 5.

insert

Schedule task 2 on day 2

Process the second task (task 2). It has no cooldown restriction yet, so schedule it on day 2. Update its next available day to day 6 (2 + 3 + 1).

💡 New tasks can be scheduled immediately, starting their own cooldown periods.

Line:

t = 2
if t in next_available:
    day = max(day, next_available[t])
next_available[t] = day + space + 1
day += 1

💡 Each task independently tracks its cooldown, allowing parallel cooldown windows.

compare

Attempt to schedule task 1 on day 3, but cooldown applies

Process the third task (task 1). The earliest next available day for task 1 is day 5, which is later than the current day 3. Update current day to 5 to respect cooldown.

💡 Cooldown forces the scheduler to wait before reusing the same task, causing idle days.

Line:

t = 1
if t in next_available:
    day = max(day, next_available[t])

💡 The scheduler must delay to avoid violating cooldown constraints.

insert

Schedule task 1 on day 5

Schedule task 1 on the updated current day 5. Update its next available day to day 9 (5 + 3 + 1). Increment day to 6.

💡 After waiting, the task is scheduled and its cooldown window is reset.

Line:

next_available[t] = day + space + 1
day += 1

💡 Cooldown windows move forward with each scheduling of the same task.

compare

Attempt to schedule task 2 on day 6

Process the fourth task (task 2). Its earliest next available day is day 6, which matches the current day, so schedule it immediately.

💡 When current day meets cooldown end, the task can be scheduled without delay.

Line:

t = 2
if t in next_available:
    day = max(day, next_available[t])

💡 Cooldowns allow scheduling as soon as the cooldown period ends.

insert

Schedule task 2 on day 6

Schedule task 2 on day 6 and update its next available day to day 10 (6 + 3 + 1). Increment day to 7.

💡 Cooldown for task 2 is updated after scheduling, delaying its next occurrence.

Line:

next_available[t] = day + space + 1
day += 1

💡 Cooldown windows are task-specific and move forward with each scheduling.

insert

Schedule task 3 on day 7

Process the fifth task (task 3). It has no cooldown restriction, so schedule it immediately on day 7. Update its next available day to day 11 (7 + 3 + 1). Increment day to 8.

💡 New tasks can be scheduled immediately, starting their cooldown windows.

Line:

t = 3
if t in next_available:
    day = max(day, next_available[t])
next_available[t] = day + space + 1
day += 1

💡 Tasks without prior cooldowns schedule immediately and start cooldown tracking.

compare

Attempt to schedule task 1 on day 8, cooldown applies

Process the sixth task (task 1). Its earliest next available day is day 9, which is later than current day 8. Update current day to 9 to respect cooldown.

💡 Cooldown forces waiting again before scheduling task 1.

Line:

t = 1
if t in next_available:
    day = max(day, next_available[t])

💡 The algorithm enforces cooldowns by advancing the current day when necessary.

insert

Schedule task 1 on day 9

Schedule task 1 on day 9 and update its next available day to day 13 (9 + 3 + 1). Increment day to 10, finishing scheduling all tasks.

💡 Final scheduling step updates cooldown and completes the task list.

Line:

next_available[t] = day + space + 1
day += 1

💡 The last task scheduling determines the total schedule length.

reconstruct

Return final answer

All tasks have been scheduled. Return the last scheduled day minus one (10 - 1 = 9) as the total number of days needed to complete all tasks with cooldowns.

💡 The final answer reflects the total schedule length including idle days.

Line:

return day - 1

💡 The algorithm's output is the total days required to schedule all tasks respecting cooldowns.

def task_scheduler_optimized(tasks, space):
    next_available = {}  # STEP 1: Initialize cooldown map
    day = 1  # STEP 1: Start at day 1
    for i, t in enumerate(tasks):
        if t in next_available:
            day = max(day, next_available[t])  # STEP 4/6/9: Update day if cooldown applies
        next_available[t] = day + space + 1  # STEP 2/5/7/8/10: Update next available day
        day += 1  # STEP 2/5/7/8/10: Move to next day
    return day - 1  # STEP 11: Return total days

if __name__ == '__main__':
    tasks = [1,2,1,2,3,1]
    space = 3
    print(task_scheduler_optimized(tasks, space))  # Expected output: 9

📊

Task Scheduler II (Cooldown Tracking) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step execution reveals how the algorithm greedily schedules tasks while respecting cooldowns, which is hard to grasp from code alone.

setupmin-heap

empty heap

Added: {"day":1,"next_available":{}}

insertmin-heap

1

0

Added: {"day":2,"next_available":{"1":5}}

insertmin-heap

1

0

2

1

Added: {"day":3,"next_available":{"1":5,"2":6}}

comparemin-heap

1

0

2

1

1

2

Added: {"day":5,"next_available":{"1":5,"2":6}}

insertmin-heap

1

0

2

1

1

2

Added: {"day":6,"next_available":{"1":9,"2":6}}

comparemin-heap

1

0

2

1

1

2

2

3

Added: {"day":6,"next_available":{"1":9,"2":6}}

insertmin-heap

1

0

2

1

1

2

2

3

Added: {"day":7,"next_available":{"1":9,"2":10}}

insertmin-heap

1

0

2

1

1

2

2

3

3

4

Added: {"day":8,"next_available":{"1":9,"2":10,"3":11}}

comparemin-heap

1

0

2

1

1

2

2

3

3

4

1

5

Added: {"day":9,"next_available":{"1":9,"2":10,"3":11}}

insertmin-heap

1

0

2

1

1

2

2

3

3

4

1

5

Added: {"day":10,"next_available":{"1":13,"2":10,"3":11}}

peekmin-heap

1

0

2

1

1

2

2

3

3

4

1

5

Added: 9

Key Takeaways

✓ The algorithm greedily schedules each task on the earliest possible day respecting cooldowns.

This insight is hard to see from code alone because the day variable updates conditionally and the cooldown map is implicit.

✓ Cooldowns are tracked independently per task, allowing parallel cooldown windows.

Visualizing the next available days for each task clarifies how tasks do not block each other unnecessarily.

✓ Idle days occur when the current day must advance to satisfy cooldown constraints before scheduling a task again.

The visualization makes explicit when and why the scheduler waits, which is subtle in code.

Practice

1. Given the following Python code for MedianFinder, what is the median after adding numbers 1, 5, and 2 in that order?

easy

A. 1.5

B. 2.0

C. 2

D. 3

Solution

1. Step 1: Insert 1

   low = [-1], high = [], median = 1 (only one element)

2. Step 2: Insert 5

   5 > 1, so push to high: high = [5], low = [-1]. Balanced heaps, median = (1 + 5)/2 = 3.0

3. Step 3: Insert 2

   2 <= 5 but > 1, so push to low: low = [-2, -1], high = [5]. Balance: low_size=2, high_size=1, median = top of low = 2.0

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Median after 3 inserts is 2.0 -> [OK]

Hint: Median after odd inserts is top of larger heap [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Incorrect median calculation for odd number of elements
• Confusing max-heap sign inversion

2. You are given an array of integers where you can perform operations to minimize the difference between the maximum and minimum elements. The operations allowed are doubling odd numbers once and halving even numbers multiple times. Which algorithmic approach guarantees finding the minimum possible deviation efficiently?

easy

A. Using a max-heap to iteratively reduce the maximum element while tracking the minimum

B. Brute force recursion trying all combinations of doubling and halving

C. Sorting the array and using a sliding window to find the minimal range

D. Dynamic programming to store states of all possible values after operations

Solution

1. Step 1: Understand problem constraints and operations

   The problem allows doubling odd numbers once and halving even numbers multiple times to minimize deviation.

2. Step 2: Identify approach that efficiently tracks max and min values

   Using a max-heap allows quick access to the current maximum, which can be reduced by halving, while tracking the minimum seen so far.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max-heap approach efficiently updates max and min values [OK]

Hint: Max-heap efficiently tracks max element for reduction [OK]

Common Mistakes:

• Thinking sorting + two pointers always works despite operations changing values
• Assuming brute force is feasible for large inputs
• Believing DP is needed despite no overlapping subproblems

3. Given the following Python code implementing the optimal two heaps approach for finding next intervals, what is the final returned result for the input intervals = [(2,3), (3,4), (1,2)]?

easy

A. [2, 0, 1]

B. [0, -1, 1]

C. [-1, -1, -1]

D. [1, -1, 0]

Solution

1. Step 1: Initialize heaps and result

   max_start_heap = [(-3,1), (-2,0), (-1,2)], max_end_heap = [(-4,1), (-3,0), (-2,2)], result = [-1, -1, -1]

2. Step 2: Process max_end_heap

   Pop (-4,1): max_start_heap top is -3 < 4, continue no update.
   Pop (-3,0): max_start_heap top -3 >= 3, pop candidates with start >= 3: (-3,1). min_start= -3, min_idx=1, result[0]=1.
   Push back unused candidates (none).
   Pop (-2,2): max_start_heap top -2 >= 2, pop candidates (-2,0), (-1,2). min_start= -1, min_idx=2, result[2]=2.
   Push back (-2,0).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches expected output for given input [OK]

Hint: Track heap pops carefully to find correct indices [OK]

Common Mistakes:

• Off-by-one in indices
• Not pushing back unused intervals
• Confusing start and end heaps

4. Consider the following buggy code snippet for sliding window median using a balanced sorted list. Which line contains the subtle bug that causes incorrect median results for even-sized windows?

medium

A. Line with 'return float(window[k // 2 - 1] + window[k // 2])'

B. Line with 'bisect.insort_left(window, nums[i])'

C. Line with 'idx = bisect.bisect_left(window, nums[i - k])'

D. Line with 'window = sorted(nums[:k])'

Solution

1. Step 1: Analyze median calculation for even k

   Median for even k is average of two middle elements, so sum must be divided by 2.

2. Step 2: Identify bug

   Line returning sum without division causes median to be twice the correct value.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing division by 2 in even median calculation [OK]

Hint: Even median requires averaging two middle elements [OK]

Common Mistakes:

• Forgetting to divide sum by 2 for even k median
• Incorrect index calculation for median
• Wrong removal or insertion causing imbalance

5. What is the time complexity of the optimal max-heap based algorithm for minimizing deviation in an array of size n with maximum element M?

medium

A. O(n^2)

B. O(n log M)

C. O(n log n)

D. O(n log n * log M)

Solution

1. Step 1: Analyze heap operations per element

   Each element is pushed once initially, O(n log n). Then max elements are halved repeatedly, up to log M times.

2. Step 2: Combine heap operations and halving steps

   Each halving involves a pop and push on heap, each O(log n), repeated up to log M times per element, total O(n log n * log M).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Complexity accounts for heap operations and repeated halving [OK]

Hint: Repeated halving causes extra log M factor multiplied by heap ops [OK]

Common Mistakes:

• Ignoring the log M factor from repeated halving
• Confusing n log n with n log M
• Assuming quadratic complexity due to nested loops