Total Run Time of Ordered Tasks with a Per-Type Cooldown
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
A single worker runs a list of tasks in exactly the order given. Each task is labeled by its type, an uppercase letter, so the list is 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, and the worker sits idle while it waits. Tasks may not be reordered. Return the total time needed to finish all the tasks.
### Function Signature
```python
def total_run_time(tasks: str, cooldown: int) -> int:
```
### Rules
- Time starts at `0`. The worker runs one task at a time, and every task takes exactly `1` time unit (the task duration is not part of the input, so this version fixes it at one unit).
- Tasks run in the given order: a task cannot start before the previous task in the string has finished.
- 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.
- Every task starts as early as these rules allow. Return the time at which the last task finishes, 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: 11
```
`A` runs in `[0, 1)` and the first `B` in `[1, 2)`. The second `B` cannot start before `2 + 3 = 5`, so the worker idles and runs it in `[5, 6)`. The first `C` runs in `[6, 7)`; the second `C` must wait until `7 + 3 = 10` and runs in `[10, 11)`.
**Example 2**
```text
Input: tasks = "ABCA", cooldown = 2
Output: 4
```
The first `A` finishes at `1`, so the second `A` may start at `1 + 2 = 3`, which is exactly when `B` and `C` have finished. There is no idle time.
**Example 3**
```text
Input: tasks = "ABAB", cooldown = 2
Output: 5
```
`A` runs in `[0, 1)` and `B` in `[1, 2)`. The second `A` must wait until `1 + 2 = 3` and runs in `[3, 4)`; the second `B` may start at `2 + 2 = 4` and runs in `[4, 5)`.
Overview: Tasks labeled by type must run in a fixed order, each taking one time unit, and two tasks of the same type need a cooldown gap between them. Compute the total time until the last task finishes. It tests careful simulation, per-type bookkeeping and edge cases such as an empty input or a zero cooldown.
A single worker runs a list of tasks in exactly the order given. Each task is labeled by its type, an uppercase letter, so the list is 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, and the worker sits idle while it waits. Tasks may not be reordered.
Implement `total_run_time(tasks, cooldown)`, which returns the total time needed to finish all the tasks under these rules:
- Time starts at `0`. The worker runs one task at a time, and every task takes exactly `1` time unit.
- Tasks run in the given order: a task cannot start before the previous task in the string has finished.
- 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.
- Every task starts as early as these rules allow.
Return the time at which the last task finishes, or `0` if `tasks` is empty.
**Example 1**
```text
Input: tasks = "ABBCC", cooldown = 3
Output: 11
```
`A` runs in `[0, 1)` and the first `B` in `[1, 2)`. The second `B` cannot start before `2 + 3 = 5`, so the worker idles and runs it in `[5, 6)`. The first `C` runs in `[6, 7)`; the second `C` must wait until `7 + 3 = 10` and runs in `[10, 11)`.
**Example 2**
```text
Input: tasks = "ABCA", cooldown = 2
Output: 4
```
The first `A` finishes at `1`, so the second `A` may start at `1 + 2 = 3`, which is exactly when `B` and `C` have finished. There is no idle time.
**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 never exceeds `2^31 - 1` and fits in a 32-bit signed integer (`int` in Java and C++).
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: ('', 5)
Expected Output: 0
Explanation: Empty task list: nothing runs, so the answer is 0.
Input: ('Q', 10000)
Expected Output: 1
Explanation: Single task with the maximum cooldown finishes at time 1; the cooldown never applies.
Hints
- Tasks cannot be reordered, so walk through them in the given order and decide only when each one starts.
- A task's earliest start depends on when the previous task in the string finished and on when the most recent task of the same type finished. What do you need to remember to know the second one?
- Check the boundary: if a task of type X finished at time f, starting the next X at exactly f + cooldown is allowed.