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 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. Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return -1
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

print(canCompleteCircuit(gas, cost))

easy

A. -1

B. 0

C. 1

D. 2

Solution

1. Step 1: Compute net array

   net = [2-3, 3-4, 4-3] = [-1, -1, 1], sum(net) = -1 which is less than 0, so return -1 immediately.

2. Step 2: Check sum(net)

   Since sum(net) < 0, no start station can complete the circuit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of net gas is negative, no solution exists [OK]

Hint: Sum net gas < 0 means no solution [OK]

Common Mistakes:

• Forgetting to check total gas vs cost
• Misindexing prefix sums
• Returning wrong start index

3. You are given a list of sticks with different lengths. You want to connect all sticks into one by repeatedly merging any two sticks, paying a cost equal to the sum of their lengths each time. Which algorithmic approach guarantees the minimum total cost to connect all sticks?

easy

A. Dynamic Programming that tries all possible merge sequences to find the minimum cost

B. Greedy algorithm using a min-heap to always merge the two shortest sticks first

C. Sorting the sticks once and merging them in sorted order from smallest to largest

D. Greedy algorithm that merges the two longest sticks first to reduce future costs

Solution

1. Step 1: Understand the problem goal

   The goal is to minimize the total cost of merging sticks, where each merge cost equals the sum of the two sticks merged.

2. Step 2: Identify the optimal strategy

   Merging the two shortest sticks first at each step minimizes incremental cost and leads to the global minimum total cost. This is efficiently done using a min-heap.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap merges shortest sticks first -> minimal total cost [OK]

Hint: Always merge shortest sticks first for minimal cost [OK]

Common Mistakes:

• Merging longest sticks first thinking it reduces future costs
• Sorting once and merging in order without reordering after merges
• Assuming brute force is needed for minimal cost

4. You are given a numeric string and an integer k. The task is to remove exactly k digits from the string so that the resulting number is the smallest possible. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Backtracking to try all combinations of digits to remove

B. Dynamic Programming that tries all subsequences of length n-k and picks the smallest

C. Sorting the digits and removing the largest k digits

D. Greedy algorithm using a stack to maintain a monotonically increasing sequence of digits

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing digits to minimize the resulting number, which suggests a greedy approach to decide which digits to remove as we scan the string.

2. Step 2: Why greedy with stack works

   The stack-based greedy approach maintains a monotonically increasing sequence by popping larger digits when a smaller digit is encountered, ensuring the smallest possible prefix at each step.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy stack approach is known optimal for this problem [OK]

Hint: Monotonic stack ensures smallest prefix greedily [OK]

Common Mistakes:

• Assuming sorting digits works ignores digit order
• Thinking DP is needed for this greedy problem
• Trying brute force is too slow for large inputs

5. What is the time complexity of the optimal greedy algorithm for the wiggle subsequence problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because it scans the list once, updating counters based on difference signs

B. O(2^n) because it explores all subsequences recursively

C. O(n log n) due to sorting or binary search steps involved

D. O(n^2) because it compares each element with all previous elements

Solution

1. Step 1: Analyze algorithm operations

   The greedy algorithm iterates through the list once, computing differences and updating counters in O(1) time per element.

2. Step 2: Address common misconceptions

   Some candidates confuse it with brute force or DP approaches, thinking it compares pairs or explores subsequences exponentially, leading to O(n^2) or O(2^n) assumptions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per element -> O(n) [OK]

Hint: Single pass with constant updates -> O(n)

Common Mistakes:

• Confusing with brute force exponential time
• Assuming nested loops for comparisons
• Thinking sorting is involved