Task Scheduler (CPU Cooling)

▶

Steps

setup

Count task frequencies

Count how many times each task appears using a frequency map.

💡 Knowing task frequencies is essential to prioritize tasks with the highest counts first.

Line:

freq = Counter(tasks)

💡 Frequency counting reveals the workload distribution among tasks.

setup

Build max-heap from frequencies

Convert frequencies into a max-heap by negating counts and heapifying.

💡 Max-heap allows quick access to the task with the highest remaining frequency.

Line:

max_heap = [-cnt for cnt in freq.values()]
heapq.heapify(max_heap)

💡 Using negative counts simulates a max-heap with Python's min-heap implementation.

traverse

Start first cycle of scheduling (n+1=3 units)

Begin a cycle to schedule up to n+1 tasks or idle slots.

💡 Each cycle represents a block of time where tasks must be spaced by cooling interval.

Line:

for _ in range(n + 1):

💡 The cycle length enforces the cooling period between identical tasks.

delete

Pop task with highest frequency (-3) from heap

Pop the most frequent task (count -3) from the heap to schedule it.

💡 Scheduling the most frequent task first reduces total idle time.

Line:

cnt = heapq.heappop(max_heap)

💡 Heap pop gives the next task to schedule based on remaining count.

insert

Decrease frequency and store for re-adding

Decrease the popped task's count by 1 and store it if still remaining.

💡 Tasks must be re-added to heap if they have remaining executions.

Line:

if cnt + 1 < 0:
    temp.append(cnt + 1)

💡 Decrementing frequency tracks progress of task completion.

traverse

Advance cycle index to 1 and pop next task

Move to next cycle unit and pop next highest frequency task (-3).

💡 Scheduling different tasks in the same cycle avoids cooling conflicts.

Line:

for _ in range(n + 1):
    if max_heap:
        cnt = heapq.heappop(max_heap)

💡 Heap ensures next task chosen is highest frequency available.

insert

Decrease frequency of second task and store

Decrease count from -3 to -2 and store for re-adding.

💡 Tasks with remaining counts must be re-added to heap for future cycles.

Line:

if cnt + 1 < 0:
    temp.append(cnt + 1)

💡 Tracking remaining counts ensures all tasks are scheduled fully.

traverse

Cycle index 2: no tasks left to pop, idle slot inserted

No tasks left in heap this cycle step, so idle time is counted.

💡 Idle slots fill cooling intervals when no tasks can be scheduled.

Line:

else:
    break

💡 Idle time is necessary to respect cooling constraints.

insert

Push remaining tasks back into heap

Re-add tasks with remaining counts (-2, -2) back into the heap.

💡 Reinserting tasks allows them to be scheduled in future cycles.

Line:

for item in temp:
    heapq.heappush(max_heap, item)

💡 Heap is updated with tasks still needing execution.

prune

Update total time after first cycle

Add n+1=3 units to total time since heap is not empty.

💡 Full cycle time is counted when tasks remain to schedule.

Line:

time += cycle if not max_heap else n + 1

💡 Total time accounts for both task execution and idle slots.

traverse

Start second cycle of scheduling

Begin next cycle of n+1=3 units to schedule tasks again.

💡 Each cycle tries to schedule as many tasks as possible.

Line:

for _ in range(n + 1):

💡 Repeated cycles continue until all tasks are scheduled.

delete

Pop task with frequency -2

Pop task with highest frequency -2 to schedule it.

💡 Scheduling continues with tasks having remaining counts.

Line:

cnt = heapq.heappop(max_heap)

💡 Heap pop always picks the next most frequent task.

insert

Decrease frequency and store for re-adding

Decrease count from -2 to -1 and store for re-adding.

💡 Tasks with remaining counts continue cycling.

Line:

if cnt + 1 < 0:
    temp.append(cnt + 1)

💡 Decrementing frequency tracks task progress.

delete

Pop second task in cycle

Pop next task with frequency -2 to schedule it.

💡 Scheduling multiple tasks per cycle maximizes CPU usage.

Line:

cnt = heapq.heappop(max_heap)

💡 Heap ensures fair scheduling of tasks with equal frequency.

insert

Decrease frequency and store for re-adding

Decrease count from -2 to -1 and store for re-adding.

💡 Tasks continue cycling until fully scheduled.

Line:

if cnt + 1 < 0:
    temp.append(cnt + 1)

💡 Tracking remaining counts is key to completion.

traverse

Cycle index 2: no tasks left, idle inserted

No tasks left to pop this cycle step, so idle time is counted.

💡 Idle time fills cooling interval when no tasks available.

Line:

else:
    break

💡 Idle slots are necessary to respect cooling constraints.

insert

Push remaining tasks (-1, -1) back into heap

Re-add tasks with frequency -1 back into the heap.

💡 Tasks still need to be scheduled until count reaches zero.

Line:

for item in temp:
    heapq.heappush(max_heap, item)

💡 Heap updated with tasks still needing execution.

prune

Update total time after second cycle

Add full cycle length (3) to total time since heap not empty.

💡 Total time accumulates including idle and execution time.

Line:

time += cycle if not max_heap else n + 1

💡 Total time reflects all cycles until completion.

traverse

Start third cycle of scheduling

Begin final cycle to schedule remaining tasks.

💡 Final cycle schedules last remaining tasks.

Line:

for _ in range(n + 1):

💡 Scheduling continues until heap is empty.

delete

Pop and schedule last two tasks

Pop tasks with frequency -1 and schedule them, no re-adding needed.

💡 Tasks complete when frequency reaches zero.

Line:

cnt = heapq.heappop(max_heap)
if cnt + 1 < 0:
    temp.append(cnt + 1)

💡 Scheduling finishes when all tasks have zero remaining count.

prune

Update total time after final cycle

Add cycle count (2) to total time since heap is empty after scheduling.

💡 Final cycle may be shorter than n+1 if tasks finish early.

Line:

time += cycle if not max_heap else n + 1

💡 Total time reflects exact scheduling duration including idle.

from collections import Counter
import heapq

def leastInterval(tasks, n):
    freq = Counter(tasks)  # STEP 1
    max_heap = [-cnt for cnt in freq.values()]  # STEP 2
    heapq.heapify(max_heap)  # STEP 2
    time = 0
    while max_heap:  # STEP 3
        temp = []
        cycle = 0
        for _ in range(n + 1):  # STEP 3
            if max_heap:
                cnt = heapq.heappop(max_heap)  # STEP 4,6,12,14,20
                if cnt + 1 < 0:
                    temp.append(cnt + 1)  # STEP 5,7,13,15
                cycle += 1
            else:
                break  # STEP 8,16
        for item in temp:
            heapq.heappush(max_heap, item)  # STEP 9,17
        time += cycle if not max_heap else n + 1  # STEP 10,18,21
    return time

if __name__ == '__main__':
    print(leastInterval(['A','A','A','B','B','B'], 2))  # Output: 8

📊

Task Scheduler (CPU Cooling) - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the greedy approach picks the most frequent tasks first and respects the cooling interval, which is hard to grasp from code alone.

record

A:3

0

B:3

1

Result: {}

record

-3

0

-3

1

Result: {}

traverse

cycle_index

-3

0

-3

1

Result: 0

move_left

cycle_index

-3

0

Result: 0

record

cycle_index

-3

0

Result: 0

move_left

Result: 0

record

Result: 0

record

Result: 0

insert

-2

0

-2

1

Result: 3

record

-2

0

-2

1

Result: 3

traverse

cycle_index

-2

0

-2

1

Result: 3

move_left

cycle_index

-2

0

Result: 3

record

cycle_index

-2

0

Result: 3

move_left

Result: 3

record

Result: 3

record

Result: 3

insert

-1

0

-1

1

Result: 6

record

-1

0

-1

1

Result: 6

traverse

cycle_index

-1

0

-1

1

Result: 6

move_left

Result: 6

record

Result: 8

Key Takeaways

✓ The greedy approach schedules the most frequent tasks first to minimize idle time.

This insight is difficult to see from code alone because the heap operations and cycle logic are abstract; visualization shows the priority clearly.

✓ The cycle length of n+1 enforces the cooling interval by limiting how many tasks can be scheduled before repeating.

Seeing the cycle iteration and idle insertions visually clarifies why the cooling interval affects scheduling order.

✓ Idle slots appear only when fewer than n+1 tasks are available to schedule, ensuring the cooling constraint is respected.

The visualization shows exactly when and why idle times are inserted, which is subtle in code.

Practice

1. You have a list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?

easy

A. Greedy algorithm by sorting greed factors and cookie sizes, then assigning smallest sufficient cookie to each child

B. Dynamic Programming to try all possible assignments and pick the best

C. Brute force nested loops checking every cookie for every child without sorting

D. Divide and Conquer by splitting children and cookies and merging results

Solution

1. Step 1: Understand problem constraints

   Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.

2. Step 2: Identify optimal approach

   Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy sorting approach is classic for assignment problems [OK]

Hint: Sort both arrays and assign greedily [OK]

Common Mistakes:

• Thinking brute force is needed for optimality
• Assuming DP is required
• Ignoring sorting leads to suboptimal matches

2. The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] > prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] < prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

medium

A. Line with 'while i < n - 1 and prices[i] < prices[i + 1]:'

B. Line with 'valley = prices[i]'

C. Line with 'while i < n - 1 and prices[i] > prices[i + 1]:'

D. Line with 'profit += peak - valley'

Solution

1. Step 1: Compare with correct condition

   The correct condition should be prices[i] >= prices[i + 1] to skip equal or descending prices.

2. Step 2: Identify bug impact

   Using strict '>' misses equal prices, causing incorrect valley selection and possibly negative profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing '>' to '>=' fixes edge cases with flat prices [OK]

Hint: Check comparison operators in loops for off-by-one errors [OK]

Common Mistakes:

• Using strict inequalities causing missed equal prices
• Adding negative differences to profit
• Off-by-one errors causing index out of range

3. Identify the bug in the following code snippet for the Maximum Units on a Truck problem:

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1])  # Sort ascending instead of descending
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

medium

A. Line 2: Sorting boxTypes in ascending order instead of descending

B. Line 5: Missing check for truckSize == 0

C. Line 7: Incorrect calculation of take using min(boxes, truckSize)

D. Line 8: Incorrect update of totalUnits by multiplying take and units

Solution

1. Step 1: Examine sorting order

   Sorting ascending by units per box causes picking boxes with lowest units first, leading to suboptimal total units.

2. Step 2: Verify other lines

   Check for early stopping (line 5) is correct; min calculation and totalUnits update are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order is critical for greedy correctness [OK]

Hint: Sort descending by units per box to maximize units [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Forgetting to break when truckSize=0
• Off-by-one in min calculation

4. Suppose the Gas Station problem is modified so that you can refill gas multiple times at the same station (i.e., unlimited reuse), and you want to find if any start station allows completing the circle with this new rule. Which approach correctly adapts to this variant?

hard

A. Check if total gas is at least total cost; if yes, return any station since reuse allows completion

B. Modify the algorithm to allow multiple passes over the stations until tank is non-negative

C. Use a graph cycle detection algorithm to find a feasible cycle with unlimited refills

D. Use the original greedy approach without changes; it still works correctly

Solution

1. Step 1: Understand unlimited refill effect

   With unlimited refills, the only constraint is total gas >= total cost; any station can be start.

2. Step 2: Simplify solution

   Since reuse removes the need to track tank drops, just check total gas vs cost and return any index if feasible.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Unlimited refill means any station works if total gas suffices [OK]

Hint: Unlimited refill means total gas check suffices [OK]

Common Mistakes:

• Trying to simulate multiple passes
• Using original greedy without adaptation
• Overcomplicating with graph algorithms

5. Suppose the problem is modified so that dominoes can be rotated multiple times (reused) to achieve uniformity, or the arrays can contain values outside 1-6. Which approach correctly adapts the solution?

hard

A. Check all unique values appearing in either array as candidates with early exit

B. Continue checking only the first domino's two values as candidates, ignoring others

C. Use dynamic programming to track rotations for all possible values 1 to 6 only

D. Sort arrays and greedily pick the most frequent value to minimize rotations

Solution

1. Step 1: Identify candidate values

   With values outside 1-6 and reuse allowed, candidates are all unique values in A and B, not just first domino.

2. Step 2: Check feasibility for each candidate

   For each candidate, verify if all dominoes can be rotated to match it, counting minimal rotations.

3. Step 3: Early exit optimization

   Stop checking candidates as soon as a valid minimal rotation count is found.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Checking all unique values covers extended domain and reuse [OK]

Hint: Check all unique values when domain expands [OK]

Common Mistakes:

• Checking only first domino candidates
• Limiting candidates to 1-6 values only