Task Scheduler
Asked at Google, Meta, Amazon, Microsoft, Apple, LinkedIn
Problem
Given a char array representing CPU tasks and a cooldown interval n, return the least number of intervals the CPU will take to finish all tasks. Each task takes one interval. The same task must have at least n intervals between its occurrences.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Medium | View all LinkedIn questions → |
How to Think About It
The most frequent task determines the minimum length. Calculate idle slots based on the max frequency.
Greedy: schedule the most frequent tasks first, then fill gaps with other tasks.
Formula: (maxFreq - 1) × (n + 1) + countOfMaxFreq. This accounts for the cooldown gaps between the most frequent tasks.
If there are enough different tasks to fill all idle slots, the answer is simply len(tasks). No idle time needed.
Visual walkthrough for tasks=["A","A","A","B","B","B"], n=2:
maxFreq=3 (A and B both have 3).
countOfMaxFreq=2 (A and B).
Formula: (3-1)×(2+1)+2 = 2×3+2 = 8.
Schedule: A _ _ A _ _ A (3 A's with 2 gaps each)
Fill gaps: A B _ A B _ A B (B fills some gaps, but we need 8 intervals)
Actually: A B _ A B _ A B = 8 intervals. ✓
Edge cases: n=0 (return len(tasks)), single task type, all unique tasks.
Optimal Approach
Step 1: Count task frequencies.
Step 2: Find max frequency (maxFreq) and count of tasks with that frequency.
Step 3: Return max(len(tasks), (maxFreq - 1) × (n + 1) + countOfMaxFreq).
The max ensures we don't undercount when there are enough tasks to avoid idle time.
Time: O(n) — count frequencies. Space: O(1) — at most 26 task types.
What Trips People Up in Real Interviews
Confusing this with "rearrange string so no two adjacent are same." That's a different problem (rearrange string). This one has a cooldown constraint.
Not using the formula. The minimum intervals = max(len(tasks), (maxFreq - 1) × (n + 1) + countOfMaxFreq). Don't simulate the scheduling.
Forgetting that the answer is at least len(tasks). If there are enough tasks to fill all gaps, no idle time is needed.
Not handling the case where n = 0. Return len(tasks) — no cooldown needed.
Miscounting tasks with max frequency. If multiple tasks share the max frequency, they all go in the last "frame." The formula adds countOfMaxFreq, not 1 — forgetting this underestimates the result.
Solution Code
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_freq = max(freq.values())
max_count = sum(1 for v in freq.values() if v == max_freq)
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)Frequently Asked Questions
What is the Task Scheduler problem?
Given a char array representing CPU tasks and a cooldown interval n, return the least number of intervals the CPU will take to finish all tasks. Each task takes one interval. The same task must have at least n intervals between its occurrences.
How do you solve Task Scheduler?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Task Scheduler?
Task Scheduler is asked at Google, Meta, Amazon, Microsoft, Apple, LinkedIn. It is a medium difficulty problem.
What are common mistakes on Task Scheduler?
- Confusing this with "rearrange string so no two adjacent are same." That's a different problem (rearrange string). This one has a cooldown constraint.
- Not using the formula. The minimum intervals = max(len(tasks), (maxFreq - 1) × (n + 1) + countOfMaxFreq). Don't simulate the scheduling.
- Forgetting that the answer is at least len(tasks). If there are enough tasks to fill all gaps, no idle time is needed.
- Not handling the case where `n = 0`. Return len(tasks) — no cooldown needed.
- Miscounting tasks with max frequency. If multiple tasks share the max frequency, they all go in the last "frame." The formula adds countOfMaxFreq, not 1 — forgetting this underestimates the result.