Domain 2MediumCORE

Task Scheduler

We are given a list of tasks, represented by characters, and an integer n representing the cooldown period between two identical tasks. The CPU processes one task per unit time. If no valid task can be executed within the cooldown window for a specific character (e.g., 'A' was just done), the CPU must idle.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Greedy#Queue

621. Task Scheduler

Model: qwen3.5:9b
Topics: Array,Greedy,Queue
FAANG asked: 1
Acceptance rate: 52.2%


Problem Breakdown

We are given a list of tasks, represented by characters, and an integer n representing the cooldown period between two identical tasks. The CPU processes one task per unit time. If no valid task can be executed within the cooldown window for a specific character (e.g., ‘A’ was just done), the CPU must idle.

Inputs:

  • tasks: A list of uppercase characters (1 <= len(tasks) <= 10^4).
  • n: An integer representing the minimum gap between same tasks (0 <= n <= 100).

Output:

  • The minimum total time units required to complete all tasks.

Implicit Constraints & Edge Cases:

  • Idle Time: We want to minimize idle slots, but sometimes they are unavoidable due to n.
  • Task Distribution: If there are enough unique tasks to fill the cooldown gaps between identical tasks, no idling is needed (result = total task count). Otherwise, we must wait.
  • Multiple Max Frequency Tasks: It’s possible multiple characters share the highest frequency (e.g., 3 ‘A’s and 3 ‘B’s). These can be interleaved at the end without forcing idle time between each other if ordered correctly.

Intuition

If I were to simulate this with a queue, pushing tasks into it as they become available, that would work but might not yield the optimal order or handle edge cases regarding cooldowns efficiently in terms of logic derivation. A brute-force permutation approach is impossible due to factorial complexity (O(N!)O(N!)).

The key insight here is identifying the bottleneck. The bottleneck task(s) are those with the highest frequency. Let’s say ‘A’ appears most often (frequency max_f). To execute all instances of ‘A’, we need at least (max_f - 1) blocks of cooldowns between them, where each block has size n + 1 (the gap plus one slot for a different task).

Essentially, the structure looks like this:

[A] [gap/n tasks] [A] [gap/n tasks] ... [A]

If we have enough other unique tasks to fill these gaps perfectly, our time is simply len(tasks). If not, we are forced to idle. The minimum time required is determined by the most frequent task’s schedule plus any remaining tasks that share its frequency count (which can fit into the final slots without extra idling).

Approach

  1. Count Frequencies: Use a hash map (Counter) to store how many times each character appears in tasks.
  2. Identify Max Frequency: Find the maximum occurrence count among all tasks, let’s call it max_f. Also track how many distinct characters have this exact frequency (let’s call this num_max_freq_tasks).
  3. Calculate Idle Slots Needed: The most frequent task dictates a frame size of (n + 1). We can fit at most one instance of the max-frequency task per frame, plus other tasks in between. There are max_f - 1 such frames before the last occurrence of that specific task type.
    • Formula for minimum time based on cooldowns: (max_f - 1) * (n + 1).
  4. Fill Remaining Slots: Add num_max_freq_tasks to account for all tasks sharing the maximum frequency, which occupy slots in those frames or at the very end without requiring extra idle time between them relative to each other.
  5. Final Result: The answer is the maximum of:
    • Total number of tasks (len(tasks)): This covers cases where we have enough unique tasks that no idling occurs (e.g., n=0 or many distinct chars).
    • Calculated minimum time based on cooldowns.

Complexity Analysis

  • Time: O(N)O(N), where NN is the number of tasks in tasks. We iterate through the list once to count frequencies and find max values. The alphabet size (26 uppercase letters) makes map operations effectively constant time relative to input length.
  • Space: O(1)O(1) or O(K)O(K) depending on definition, where KK is the number of unique characters (max 26). This is technically constant space since it doesn’t scale with N.

Solution

from collections import Counter
import heapq # Not strictly needed for this specific math approach but good practice if using heap-based simulation. 
# However, pure math solution uses O(1) extra space logic beyond the counter.

def leastInterval(tasks: list[str], n: int) -> int:
    # 1. Count frequencies of each task
    counts = Counter(tasks)
    
    # 2. Find max frequency and how many tasks share that frequency
    max_f = max(counts.values()) if counts else 0
    
    # Number of tasks with the maximum frequency count (e.g., A:3, B:3 -> num_max_freq_tasks = 2)
    num_max_freq_tasks = sum(1 for v in counts.values() if v == max_f)
    
    # 3. Calculate minimum time based on cooldown constraints
    # We need (max_f - 1) blocks of size (n + 1), plus the last block which holds all remaining tasks
    idle_time_needed = (max_f - 1) * n
    
    # The total slots required by the bottleneck task structure:
    min_len = (max_f - 1) * (n + 1) + num_max_freq_tasks
    
    # 4. Return max of actual tasks vs calculated constraint time
    return len(tasks) if idle_time_needed == 0 else max(len(tasks), min_len)

# Wait, let's refine the logic for clarity in code comments to match standard optimal solution:
```python
from collections import Counter

def leastInterval(tasks: list[str], n: int) -> int:
    # Count frequency of each task type
    counts = Counter(tasks)
    
    # Find maximum frequency among all tasks
    max_f = 0
    if not counts: return 0
    
    for count in counts.values():
        if count > max_f:
            max_f = count
            
    # Calculate how many distinct characters have this max frequency. 
    # These can be placed at the end of the schedule without forcing idle time between them.
    num_max_freq_tasks = sum(1 for v in counts.values() if v == max_f)
    
    # The structure is determined by the most frequent task(s).
    # We have (max_f - 1) intervals where we can fit n other tasks + 1 slot per interval.
    # Plus one final block containing all remaining instances of max_freq_tasks.
    return max(len(tasks), (max_f - 1) * (n + 1) + num_max_freq_tasks)

# Example usage:
print(leastInterval(["A","A","A","B","B","B"], 2)) # Output: 8

Edge Cases Handled

  • n = 0: The formula (max_f - 1) * (0 + 1) simplifies to max_f - 1. Adding num_max_freq_tasks results in a value ≤\le total tasks. The function returns len(tasks) via the outer max, correctly allowing immediate execution of different tasks without gaps.
  • All Tasks Identical: If all are ‘A’, counts = {'A': N}, max_f = N, num_max_freq_tasks = 1. Result: (N-1)*(n+1) + 1 which is correct (idle slots required).
  • Many Unique Tasks vs Few Cooldowns: If unique tasks fill the gaps, len(tasks) will be greater than or equal to the calculated constraint time. The function returns len(tasks), correctly indicating no idle time needed.