⚡Flashcard Drill➔
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

  1. The most frequent task dictates the schedule: it must be placed max_freq times with n gaps between consecutive copies.
  2. That forms max_freq - 1 full frames of size n + 1, plus one final partial frame holding all tasks that share the maximum frequency.
  3. So the lower bound is (max_freq - 1) * (n + 1) + count_of_max_freq_tasks.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems