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 ().
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
- Count Frequencies: Use a hash map (
Counter) to store how many times each character appears intasks. - 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 thisnum_max_freq_tasks). - 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 aremax_f - 1such frames before the last occurrence of that specific task type.- Formula for minimum time based on cooldowns:
(max_f - 1) * (n + 1).
- Formula for minimum time based on cooldowns:
- Fill Remaining Slots: Add
num_max_freq_tasksto 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. - 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=0or many distinct chars). - Calculated minimum time based on cooldowns.
- Total number of tasks (
Complexity Analysis
- Time: , where 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: or depending on definition, where 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 tomax_f - 1. Addingnum_max_freq_tasksresults in a value total tasks. The function returnslen(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) + 1which 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 returnslen(tasks), correctly indicating no idle time needed.