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.