Funcia
Lv.2countinggreedymath

Task Schedule with Cooldown

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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 tt, its next task can run no earlier than t+n+1t + n + 1. Return the minimum total time (idle units included) to finish all tasks.

Examples

tasksnresult
"AAABBB"28
"AAABBB"06
"AAAAAABCDEFG"216

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

  • 1≤1 \le tasks.length ≤1,000,000\le 1{,}000{,}000, uppercase English letters only
  • 0≤0 \le n ≤1,000\le 1{,}000

Expected complexity

Time
O(L)
Space
O(1)

Examples

tasksnExpected
"AAABBB"28
"AAABBB"06
"AAAAAABCDEFG"216

Hint

Hint

Simulating time unit by unit can take about 10910^9 steps when most of the time is idle. Let MM be the highest task count and cc the number of types with that count: the answer is max⁡(tasks.length, (M−1)(n+1)+c)\max(\text{tasks.length},\ (M-1)(n+1) + c).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.