621. Task Scheduler
mediumGiven task types and a cooldown n, return the minimum CPU intervals to finish all tasks with no same-type tasks within n of each other. A frequent design-leaning interview problem.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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 in the array), 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.
Constraints
1 <= tasks.length <= 10^4tasks[i] is an upper-case English letter.0 <= n <= 100
Examples
Example 1
tasks = ["A","A","A","B","B","B"], n = 28Explanation: A -> B -> idle -> A -> B -> idle -> A -> B. There is at least 2 units of time between any two same tasks.
Example 2
tasks = ["A","C","A","B","D","B"], n = 16Explanation: A -> B -> C -> D -> A -> B. The tasks can be done without any idle time.
Example 3
tasks = ["A","A","A","B","B","B"], n = 310Explanation: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B. There are only two types of tasks, A and B, which need to take 3 units of time between them.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Greedy intuition: at each step, run the most-frequent eligible task — that's the one most likely to block the schedule later.
Hint 2
Max-heap of (count, taskType). Pop up to (n+1) distinct tasks per cycle, decrement each, push back what's not depleted.
Hint 3
Closed-form: let maxCount = frequency of the most common task, and tiedForMax = how many task types share that frequency. Answer = max(tasks.length, (maxCount - 1) * (n + 1) + tiedForMax).
Solution approach
Reveal approach
Two clean solutions. Heap simulation: build a max-heap of task counts, then per cycle pop up to n+1 distinct task types, decrement each, and push back the still-positive ones. Track total time; the cycle takes n+1 units (or less if you ran out of distinct tasks early and only count actual work + the gap if the heap isn't empty). Closed-form formula: find maxCount (count of the most-frequent task) and tiedForMax (how many distinct tasks share that count). Answer = max(tasks.length, (maxCount - 1) * (n + 1) + tiedForMax). The formula assumes you anchor the schedule around the most-frequent task and only pay idle time if there aren't enough other tasks to fill the gaps. O(n) time + O(1) space — explain the intuition and the interviewer will be happy with either.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- heap
- greedy
- counting
- math
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
Practice these live with InterviewChamp.AI
Drill Task Scheduler and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →