Minimum Run Time for Reorderable Tasks with a Per-Type Cooldown
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
A single worker must run a set of tasks, each labeled by its type, an uppercase letter, given as a string such as `"ABBCC"`. Two tasks of the same type need a cooldown between them: after a task of some type finishes, the next task of that type cannot start until `cooldown` time units have passed. Unlike the fixed-order version of this problem, the tasks may now be run in any order, and the worker may sit idle whenever it chooses. Return the minimum possible total time to finish all the tasks.
### Function Signature
```python
def min_total_run_time(tasks: str, cooldown: int) -> int:
```
### Rules
- Time starts at `0`. The worker runs one task at a time, every task takes exactly `1` time unit, and every task in `tasks` runs exactly once.
- Tasks may run in any order, and the worker may be idle between tasks.
- If a task of type `X` finished at time `f`, the next task of type `X` may start no earlier than `f + cooldown`. Tasks of other types are not affected by it.
- Return the smallest possible time at which the last task finishes, over all valid schedules, or `0` if `tasks` is empty.
### Constraints
- `0 <= len(tasks) <= 10^5`
- `tasks` consists of uppercase English letters `'A'` to `'Z'`.
- `0 <= cooldown <= 10^4`
- The answer is at most `1,000,090,000`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: tasks = "ABBCC", cooldown = 3
Output: 6
```
One optimal schedule is `B`, `C`, `A`, idle, `B`, `C`: the second `B` starts at `1 + 3 = 4` and the second `C` at `2 + 3 = 5`, finishing at `6`. Finishing at `5` is impossible: both pairs of `B` and `C` would need start times at least `4` apart within `0` to `4`, and only times `0` and `4` qualify, so the two pairs cannot both fit.
**Example 2**
```text
Input: tasks = "AAAB", cooldown = 1
Output: 5
```
One optimal schedule is `A`, `B`, `A`, idle, `A`. The three `A` tasks need start times at least `2` apart, so the last one starts no earlier than `4`.
**Example 3**
```text
Input: tasks = "ABCABC", cooldown = 1
Output: 6
```
Running the tasks in the given order already satisfies every cooldown, with no idle time, and six tasks cannot finish before time `6`.
Overview: Given tasks labeled by type and a cooldown that must pass between two runs of the same type, find the minimum total time to finish every task when they may be run in any order with idle time allowed. It tests scheduling insight, proving that a schedule is optimal, and edge cases such as a zero cooldown.
Implement `min_total_run_time(tasks, cooldown)`.
A single worker must run a set of tasks. Each task is labeled by its type, an uppercase letter, and the tasks are given as a string such as `"ABBCC"`. Two tasks of the same type need a cooldown between them: after a task of some type finishes, the next task of that type cannot start until `cooldown` time units have passed. The tasks may be run in any order, and the worker may sit idle whenever it chooses. Return the minimum possible total time to finish all the tasks.
### Rules
- Time starts at `0`. The worker runs one task at a time, every task takes exactly `1` time unit, and every task in `tasks` runs exactly once.
- Tasks may run in any order, and the worker may be idle between tasks.
- If a task of type `X` finished at time `f`, the next task of type `X` may start no earlier than `f + cooldown`. Tasks of other types are not affected by it.
- Return the smallest possible time at which the last task finishes, over all valid schedules, or `0` if `tasks` is empty.
### Constraints
- `0 <= len(tasks) <= 10^5`
- `tasks` consists of uppercase English letters `'A'` to `'Z'`.
- `0 <= cooldown <= 10^4`
- The answer is at most `1,000,090,000`, so it fits in a 32-bit signed integer and never exceeds `2^31 - 1`.
### Examples
**Example 1**
```text
Input: tasks = "ABBCC", cooldown = 3
Output: 6
```
One optimal schedule is `B`, `C`, `A`, idle, `B`, `C`: the second `B` starts at `1 + 3 = 4` and the second `C` at `2 + 3 = 5`, finishing at `6`. Finishing at `5` is impossible: both pairs of `B` and `C` would need start times at least `4` apart within `0` to `4`, and only times `0` and `4` qualify, so the two pairs cannot both fit.
**Example 2**
```text
Input: tasks = "AAAB", cooldown = 1
Output: 5
```
One optimal schedule is `A`, `B`, `A`, idle, `A`. The three `A` tasks need start times at least `2` apart, so the last one starts no earlier than `4`.
Constraints
- 0 <= len(tasks) <= 10^5
- tasks consists of uppercase English letters 'A' to 'Z'.
- 0 <= cooldown <= 10^4
- The answer is at most 1,000,090,000, so it fits in a 32-bit signed integer.
Examples
Input: ('', 2)
Expected Output: 0
Explanation: Empty tasks: nothing runs, so the answer is 0 regardless of cooldown.
Input: ('A', 5)
Expected Output: 1
Explanation: Single task finishes at time 1; the cooldown never applies.
Hints
- Because the tasks may run in any order, ask whether the positions of the letters in the input string matter at all, or only something simpler about them.
- A task occupies one time unit before its cooldown begins, so work out exactly how far apart the start times of two same-type tasks must be.
- Try small cases by hand, such as one letter repeated several times versus many distinct letters, and notice when the worker is forced to sit idle and when it never has to.
Community answers
Answer by ltloan
from collections import Counter
def min_total_run_time(tasks: str, cooldown: int) -> int:
freq=Counter(c for char in tasks)
data = [[t, f, 1] for t, f in freq.items]
sorted_data = sorted(data, key=lambda x: (-x[1], x[2]))
total_time=0
while sorted_data[0][1]>0:
total_time = max(total_time+1,sorted_data[0][2])
sorted_data[0][1]-=1
if sorted_data[0][1]>1:
sorted_data[0][2] = total_time+cooldown+1
sorted_data = sorted(data, key=lambda x: (-x[1], x[2]))
return total_time