Task Scheduler
You are given an array of CPU tasks, each represented by a character from A to Z, and a cooling interval n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
There are a total of 8 intervals.
Example 2:
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.
There are no idle intervals needed since all tasks can be interleaved.
Example 3:
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: With n = 0, no cooling is needed. Any order works and takes 6 intervals.
Examples
Example 1
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. Total of 8 intervals.
Example 2
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B. No idle intervals needed.
Example 3
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: With n = 0, no cooling is needed. Any order works and takes 6 intervals total.
Constraints
- -1 <= tasks.length <= 10^4
- -tasks[i] is an uppercase English letter
- -0 <= n <= 100
Optimal Complexity
Time
O(n)
Space
O(1)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview