Task Scheduler (CPU Cooling)

📋

Problem

Imagine a CPU that must execute a list of tasks, but it needs to cool down between identical tasks to avoid overheating. How do you schedule tasks to minimize total execution time?

Given a list of tasks represented by capital letters A to Z, and a non-negative integer n representing the cooldown period between two identical tasks, return the least number of units of times the CPU will take to finish all the tasks. The CPU can either execute a task or stay idle during a unit of time. Tasks can be executed in any order.

1 ≤ tasks.length ≤ 10^5tasks[i] is an uppercase English letter.0 ≤ n ≤ 100

Edge cases: All tasks are the same and n > 0 → output is (tasks.length - 1) * (n + 1) + 1n = 0 (no cooldown) → output is tasks.lengthTasks all unique → output is tasks.length

</>

IDE

def leastInterval(tasks: list[str], n: int) -> int:public int leastInterval(char[] tasks, int n)int leastInterval(vector<char> tasks, int n)function leastInterval(tasks, n)

def leastInterval(tasks, n):
    # Write your solution here
    pass

class Solution {
    public int leastInterval(char[] tasks, int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int leastInterval(vector<char> tasks, int n) {
    // Write your solution here
    return 0;
}

function leastInterval(tasks, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: tasks.lengthIgnoring cooldown period n and returning tasks length directly.✅ Apply idle time formula: max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount).

Wrong: maxFreq * (n + 1)Misapplying formula without subtracting 1 from maxFreq or not adding maxCount.✅ Use (maxFreq - 1) * (n + 1) + maxCount instead.

Wrong: Underestimated time due to greedy scheduling without cooldown enforcementScheduling tasks greedily without respecting cooldown leads to invalid schedules.✅ Use idle time formula or priority queue with cooldown to enforce constraints.

Wrong: Incorrect time due to treating tasks as unbounded (reusing same task multiple times in one unit)Confusing 0/1 scheduling with unbounded knapsack style reuse.✅ Decrement frequency after scheduling each task instance; do not reuse in same time unit.

Wrong: Timeout or no outputUsing brute force simulation for large inputs causing TLE.✅ Implement O(m) idle time formula or O(t log m) priority queue approach.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before tackling edge cases.

Understand common pitfalls in greedy scheduling and cooldown enforcement.

Optimize your solution to run efficiently on large inputs using frequency analysis.

t1_01basic

Input{"tasks":["A","A","A","B","B","B"],"n":2}

Expected8

⏱ Performance - must finish in 2000ms

One possible schedule is A -> B -> idle -> A -> B -> idle -> A -> B. Total time is 8.

💡 Think about the most frequent tasks and how cooldown affects scheduling.

💡 Use the formula max(total tasks length, (max frequency - 1) * (n + 1) + count of max frequency tasks).

💡 Calculate max frequency and count how many tasks have that frequency to find minimum intervals.

Why it failed: Incorrect output means misunderstanding of cooldown effect or max frequency calculation. Fix by applying the idle time formula correctly.

✓ Correctly accounts for cooldown and task frequencies.

t1_02basic

Input{"tasks":["A","A","A","B","B","C","C"],"n":2}

Expected7

⏱ Performance - must finish in 2000ms

Schedule: A -> B -> C -> A -> B -> C -> A. Total time is 7 with no idle needed.

💡 Check if tasks with lower frequency can fill idle slots.

💡 Count max frequency and number of tasks with that frequency to calculate idle slots.

💡 If idle slots are negative, total time equals tasks length.

Why it failed: Failing this test usually means not considering multiple tasks with max frequency or idle slot filling. Fix by counting max frequency tasks properly.

✓ Handles multiple max frequency tasks and idle filling correctly.

t2_01edge

Input{"tasks":[],"n":2}

Expected0

⏱ Performance - must finish in 2000ms

No tasks means no time needed.

💡 Consider the case when tasks list is empty.

💡 Return 0 immediately if no tasks to schedule.

💡 Check for empty input before processing frequencies.

Why it failed: Returning non-zero means not handling empty input correctly. Fix by adding a check for empty tasks list.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"tasks":["A"],"n":2}

Expected1

⏱ Performance - must finish in 2000ms

Single task requires only 1 unit time regardless of cooldown.

💡 Single task means no cooldown needed.

💡 Result equals tasks length when only one task.

💡 Check if tasks length is 1 and return 1 directly.

Why it failed: Incorrect output means cooldown applied unnecessarily for single task. Fix by returning tasks length when only one task.

✓ Handles single task correctly without extra idle.

t2_03edge

Input{"tasks":["A","B","C","D"],"n":0}

Expected4

⏱ Performance - must finish in 2000ms

Cooldown zero means tasks can be scheduled back-to-back, total time equals tasks length.

💡 Cooldown zero means no idle time needed.

💡 Result equals tasks length when n=0.

💡 Check if n=0 and return tasks length directly.

Why it failed: Failing this test means cooldown applied even when n=0. Fix by returning tasks length when n=0.

✓ Correctly handles zero cooldown case.

t3_01corner

Input{"tasks":["A","A","A","A"],"n":3}

Expected13

⏱ Performance - must finish in 2000ms

All tasks same with cooldown 3: (4-1)*(3+1)+1=13 units time.

💡 When all tasks are identical, cooldown forces idle slots between each.

💡 Use formula (maxFreq - 1) * (n + 1) + 1 for all identical tasks.

💡 Check if your code handles this exact boundary correctly.

Why it failed: Incorrect output means ignoring cooldown or miscalculating idle slots for identical tasks. Fix by applying the formula for all identical tasks.

✓ Correctly calculates time for all identical tasks with cooldown.

t3_02corner

Input{"tasks":["A","A","A","B","B","B","C","C"],"n":2}

Expected8

⏱ Performance - must finish in 2000ms

Greedy trap: naive greedy scheduling may fail; correct answer is 8.

💡 Greedy by always picking highest frequency task next can fail if cooldown not respected.

💡 Use idle time formula instead of naive greedy scheduling.

💡 Calculate max frequency and count tasks with max frequency to find minimum intervals.

Why it failed: Failing this test means greedy scheduling without cooldown enforcement. Fix by using idle time formula or priority queue with cooldown.

✓ Avoids greedy trap by correctly enforcing cooldown.

t3_03corner

Input{"tasks":["A","A","A","B","B","B","C","C","C"],"n":2}

Expected9

⏱ Performance - must finish in 2000ms

0/1 vs unbounded confusion: tasks can only be scheduled once each time unit; correct answer is 9.

💡 Each task instance can be scheduled only once; no unlimited reuse in one time unit.

💡 Check that you decrement frequency after scheduling each task instance.

💡 Use max frequency and count to calculate idle slots correctly.

Why it failed: Failing this test means treating tasks as unbounded or reusing tasks in same time unit. Fix by decrementing frequency per scheduled task instance.

✓ Correctly handles 0/1 scheduling constraint.

t4_01performance

Input{"tasks":["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"],"n":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=50 and 100 tasks to test O(m) or O(t log m) complexity within 2 seconds.

💡 Use frequency counting and idle time formula for O(m) solution.

💡 Avoid brute force simulation which is O(m * t) and will TLE.

💡 Use max frequency and count of max frequency tasks to compute answer efficiently.

Why it failed: TLE indicates brute force simulation with high complexity. Fix by implementing greedy formula or priority queue approach.

✓ Efficient solution with O(m) or O(t log m) complexity confirmed.

Practice

1. You have two arrays representing the top and bottom halves of dominoes. You want to make all values in one row uniform by rotating some dominoes. Which algorithmic approach guarantees an optimal solution with minimal rotations?

easy

A. Dynamic Programming that tries all possible uniform values and stores intermediate results

B. Greedy approach checking only the two candidate values from the first domino

C. Backtracking to try all rotation combinations exhaustively

D. Sorting both arrays and then matching values to minimize rotations

Solution

1. Step 1: Identify candidate values from the first domino

   The only possible uniform values are the top or bottom value of the first domino, since all dominoes must match one of these.

2. Step 2: Check feasibility and count rotations

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

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking only two candidates reduces complexity and guarantees correctness [OK]

Hint: Only two candidates from first domino suffice [OK]

Common Mistakes:

• Trying all numbers 1-6 unnecessarily
• Using DP or backtracking wasting time

2. You are given a string and need to rearrange its characters so that no two adjacent characters are the same. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm using a max heap (priority queue) to always pick the most frequent character available next

B. Dynamic Programming that counts character frequencies and tries all permutations

C. Simple sorting of characters and placing them in alternating positions without frequency checks

D. Backtracking by generating all permutations and checking adjacency constraints

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging characters so no two adjacent are the same, which demands careful ordering based on frequency.

2. Step 2: Identify approach that guarantees optimality

   Greedy approach with a max heap always picks the most frequent character available that is not the previously used one, ensuring no adjacency violation and optimal placement.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach is standard and optimal for this problem [OK]

Hint: Max heap greedily picks highest frequency char [OK]

Common Mistakes:

• Assuming simple sorting suffices
• Thinking backtracking is efficient here
• Confusing DP with greedy

3. Consider the following buggy code for candy distribution. Which line contains the subtle bug that can cause incorrect candy counts?

medium

A. Line 3: candies initialized with zeros instead of ones

B. Line 5: loop starts from 1 instead of 0

C. Line 7: candies[i] updated without checking if greater than candies[i-1]

D. Line 9: condition candies[i] <= candies[i + 1] missing

Solution

1. Step 1: Check initialization of candies array

   Line 3 initializes candies with zeros, violating the problem requirement that each child must have at least one candy.

2. Step 2: Understand impact of zero initialization

   Zero candies can cause incorrect comparisons and final sums, failing test cases where minimum is 1 per child.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialization must be at least 1 per child [OK]

Hint: Candies must start at 1, not 0 [OK]

Common Mistakes:

• Forgetting minimum candy per child
• Incorrect loop boundaries
• Missing update conditions

4. The following code attempts to remove k digits from a number string to get the smallest number. Which line contains a subtle bug that causes incorrect results on inputs with leading zeros?

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder)  # Bug here
    return result if result else '0'

medium

A. Line where digits are popped inside the for loop

B. Line where leading zeros are not stripped from the final result

C. Line where remaining digits are popped after the loop

D. Line where digits are appended to builder

Solution

1. Step 1: Identify missing leading zero removal

   The code joins builder into a string but does not strip leading zeros, which can cause incorrect output like "0012" instead of "12".

2. Step 2: Why this is a bug

   Leading zeros must be removed to get the correct smallest number representation; otherwise, the output is invalid.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding .lstrip('0') fixes the bug [OK]

Hint: Always strip leading zeros before returning result [OK]

Common Mistakes:

• Forgetting to strip leading zeros
• Removing digits incorrectly in the loop
• Not popping remaining digits when k > 0

5. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., unlimited transactions including multiple buys and sells per day). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Add all positive differences between consecutive prices and also consider zero differences as profitable

B. Sum all positive differences between consecutive days as before, no change needed

C. Use a dynamic programming approach to consider multiple transactions per day explicitly

D. Modify the code to add all positive differences between consecutive prices including zero differences

Solution

1. Step 1: Understand the new constraint

   Allowing multiple transactions per day does not change the fact that profit comes from positive price differences.

2. Step 2: Check if algorithm needs change

   Summing all positive consecutive differences already accounts for all profitable transactions, including multiple per day.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Algorithm already sums all positive increments, no modification needed [OK]

Hint: Unlimited transactions per day still sum positive differences [OK]

Common Mistakes:

• Adding zero or negative differences incorrectly
• Overcomplicating with DP when greedy suffices
• Thinking multiple transactions per day require new logic