MEDIUM NC#68 Heap / Priority Queue
621. Task Scheduler
📖 Problem
You are given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter), that is that there must be at least n units of time between any two same tasks. Return the least number of units of times that the CPU will take to finish all the given tasks.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Level-order traversal
- •Queue discipline
- •Shortest-step interpretation
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply BFS reasoning pattern
- •Apply Heap reasoning pattern
💡 Approach
- → Calculate idle time based on most frequent task
- → Idle slots = (maxFreq - 1) * n
- → Fill idle slots with other tasks
- → Time: O(n), Space: O(1) since only 26 letters
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •Calculate idle time based on most frequent task
- •Idle slots = (maxFreq - 1) * n
- •Fill idle slots with other tasks
Common Pitfalls
- •Time: O(n), Space: O(1) since only 26 letters
🧪 Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
leastInterval(['A','A','A','B','B','B'], 2); Expected:
8 Test Case 2
Not run Input:
leastInterval(['A','C','A','B','D','B'], 1); Expected:
6 Test Case 3
Not run Input:
leastInterval(['A','A','A','B','B','B'], 3); Expected:
10 📝 Code Editor
📤 Output