NeetCode #533LC-621MediumHeap / Priority QueueNC 150NC 250
← Back to All Problems#533 · #621 · Task Scheduler(任务调度器)
📌 Problem Statement & Constraints
You are given a list of CPU tasks (letters) and a cooldown
n. Identical tasks must be separated by at least n intervals; idle slots may be inserted. Return the minimum number of intervals needed to finish all tasks. Constraints: 1 <= tasks.length <= 10^4, 0 <= n <= 100.💡 Core Algorithmic Approaches
- The most frequent task dictates the schedule: it must be placed
max_freqtimes withngaps between consecutive copies. - That forms
max_freq - 1full frames of sizen + 1, plus one final partial frame holding all tasks that share the maximum frequency. - So the lower bound is
(max_freq - 1) * (n + 1) + count_of_max_freq_tasks. - The answer is the maximum of that bound and the total task count -- when there are many distinct tasks, no idle slots are needed.
💻 Benchmark Python3 Implementation
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
from collections import Counter
cnt = Counter(tasks)
max_freq = max(cnt.values())
# how many tasks share the maximum frequency
num_max = sum(1 for v in cnt.values() if v == max_freq)
# frames of size n+1, plus the tail frame
return max(len(tasks), (max_freq - 1) * (n + 1) + num_max)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m) where m is the number of distinct tasks: one counting pass.
💾 Space Complexity
O(m) for the counter.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
max(len(tasks), ...): with many distinct tasks the schedule needs no idle slots, and the frame formula alone underestimates. - Omitting
num_max: several tasks may share the maximum frequency and they all occupy the tail frame. - Simulating the schedule with a heap: it works (and is a good follow-up answer) but is O(total slots log m), far slower than the closed form.
- Assuming
n = 0: then the answer is simply the task count, which the formula also produces.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.