Reorderable Task Scheduler With Cooldown
Waymo● MediumFULLTIMEPHONE SCREENProblem statement
You are given a string tasks. Each character is a task type. You are also given an integer cooldown.
The tasks run on one machine under these rules:
- Each task takes exactly one second, and in each second the machine either runs one task or stays idle.
- You may run the tasks in any order.
- Two tasks of the same type must have at least
cooldownseconds between them. Tasks of other types and idle seconds both count toward that gap.
Return the minimum total number of seconds needed to finish every task. Do not count idle time after the last task finishes.
Function
leastRunTime(tasks: String, cooldown: int) → intExamples
Example 1
tasks = "ABBCC"cooldown = 3return = 6B and C each appear twice. Their first runs use two different seconds, so one of them starts at second 1 or later. Its second run must start at least 1 + 3 = 4 seconds after its first run starts, so at second 5 or later, and it ends at 6 or later.
The order B, C, A, idle, B, C reaches that bound: each repeated type has three seconds between its two runs. The answer is 6.
Example 2
tasks = "AAABBB"cooldown = 2return = 8A and B each appear three times. One of their first runs starts at second 1 or later. Each later run of that type starts at least 1 + 2 = 3 seconds after the previous one, so its third run starts at second 1 + 3 + 3 = 7 or later and ends at 8 or later.
The order A, B, idle, A, B, idle, A, B reaches that bound. The answer is 8.
Example 3
tasks = "AAABBCCDD"cooldown = 1return = 9The order A, B, A, C, A, D, B, C, D never runs the same type twice in a row, so no idle time is needed. All nine tasks finish in 9 seconds.
Constraints
1 <= tasks.length <= 10^4taskscontains only uppercase English letters.0 <= cooldown <= 100