Heap · LC #621
Task Scheduler
The minimum intervals = max(tasks.length, (maxFreq-1)*(n+1)+maxCount). The most-frequent task drives the frame structure; idle slots fill gaps.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a list of CPU tasks and a cooldown `n` (same task must wait `n` intervals), find the minimum number of intervals to finish all tasks.
Sample I/O
Input: tasks=["A","A","A","B","B","B"], n=2 Output: 8 (A→B→idle→A→B→idle→A→B) Input: tasks=["A","A","A","B","B","B"], n=0 Output: 6
Intuition
How to Think About It
Intuition
The most frequent task creates (maxFreq-1) mandatory waiting frames of size (n+1). Other tasks fill those frames; if they overflow, we need no idle time at all and the answer is simply tasks.length.
Core Concept
Count frequencies. maxFreq = highest frequency. maxCount = number of tasks with that frequency. Answer = max(tasks.length, (maxFreq-1)*(n+1)+maxCount). The formula models the frame structure: each frame has the most-frequent task plus n fillers or idles.
When to use
CPU scheduling with cooldowns; rate-limited job queues; process scheduling with recharge times.
When NOT to use
When you need the actual schedule (order of tasks), not just the length - use a max-heap simulation instead.
Key Insights
What to Know Cold
- The formula eliminates need for simulation: (maxFreq-1)*(n+1)+maxCount.
- max(tasks.length, formula) handles the case where tasks are dense enough to fill all idle slots.
- maxCount accounts for multiple tasks tied at maxFreq - they all fit in the final partial frame.
- n=0 means no cooldown - answer is always tasks.length.
- Heap simulation is an alternative: O(n log 26) = O(n), same asymptotic but higher constant.
1 example
Worked Examples
Minimum CPU intervals for tasks with cooldown
tasks=["A","A","A","B","B","B"], n=2 - layout: A→B→idle→A→B→idle→A→B.
Math formula: (maxFreq-1)*(n+1)+maxCount.
Output: 8
CPU/OS scheduling, distributed rate-limited workers, and API throttling all use this frame-based reasoning.