Task Schedule with Cooldown
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A factory machine must process the tasks in the string tasks; each uppercase letter is a task type and every task takes exactly
one unit of time. Tasks may be done in any order, and in each time unit the machine either processes one task or idles.
Two tasks of the same type must be at least n time units apart: if a type is processed at time , its next task can run
no earlier than . Return the minimum total time (idle units included) to finish all tasks.
Examples
| tasks | n | result |
|---|---|---|
"AAABBB" | 2 | 8 |
"AAABBB" | 0 | 6 |
"AAAAAABCDEFG" | 2 | 16 |
Example 1 — A B idle A B idle A B takes 8 units.
Example 2 — With no cooldown nothing ever idles.
Example 3 — The six As need gaps of 2; the other six tasks fill some of them, the rest is idle: 16 units.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(tasks: string, n: int) → long
Constraints
-
tasks.length, uppercase English letters only -
n
Expected complexity
- Time
- O(L)
- Space
- O(1)
Examples
| tasks | n | Expected |
|---|---|---|
"AAABBB" | 2 | 8 |
"AAABBB" | 0 | 6 |
"AAAAAABCDEFG" | 2 | 16 |
Hint
Hint
Simulating time unit by unit can take about steps when most of the time is idle. Let be the highest task count and the number of types with that count: the answer is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |