Last Task Finish Time with Limited CPUs and a Fixed Task Duration
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Tasks are scheduled to start at given times, and every task takes the same execution time. At most `max_cpus` tasks can run at the same moment, one task per CPU. A task cannot start before its scheduled time; if every CPU is busy at that time, it waits until a CPU becomes free. Return the time at which the last task finishes.
### Function Signature
```python
def last_finish_time(start_times: list[int], duration: int, max_cpus: int) -> int:
```
### Rules
- `start_times[i]` is the scheduled start time of task `i`. Each task runs on one CPU, without interruption, for exactly `duration` time units: a task that starts at time `t` finishes at time `t + duration`.
- A CPU that finishes a task at time `t` can start another task at time `t`.
- A CPU never stays idle while a task whose scheduled time has arrived is waiting.
- Waiting tasks start in order of their scheduled start times. Because every task has the same duration, the order among tasks with equal scheduled times does not change the answer.
- Return the latest finish time over all tasks.
### Constraints
- `1 <= len(start_times) <= 10^5`
- `0 <= start_times[i] <= 10^9`, integers, in no particular order
- `1 <= duration <= 10^9`
- `1 <= max_cpus <= 10^5`
- The answer can reach about `10^14`, which is beyond 2^31 - 1 but below 2^53: use 64-bit integers.
### Examples
**Example 1**
```text
Input: start_times = [1, 4, 6], duration = 5, max_cpus = 2
Output: 11
```
The task scheduled at `1` runs from `1` to `6` on one CPU, and the task scheduled at `4` runs from `4` to `9` on the other. At time `6` the first CPU is free again, so the third task runs from `6` to `11`.
**Example 2**
```text
Input: start_times = [1, 4, 6], duration = 5, max_cpus = 1
Output: 16
```
With one CPU the tasks run from `1` to `6`, from `6` to `11` and from `11` to `16`.
**Example 3**
```text
Input: start_times = [10, 0, 0, 0], duration = 3, max_cpus = 2
Output: 13
```
Two of the tasks scheduled at `0` run from `0` to `3`; the third waits and runs from `3` to `6`. The task scheduled at `10` finds a free CPU and runs from `10` to `13`.
Overview: A scheduling problem: tasks have scheduled start times, each runs for the same fixed duration, and only a limited number of CPUs can run tasks at once, so some tasks wait. Return the time at which the last task finishes. It tests simulation of limited parallel resources, in the style of meeting-room allocation.
Read the full Google Software Engineer interview experience this question came from
Tasks are scheduled to start at given times, and every task takes the same execution time, `duration`. There are `max_cpus` CPUs: at most `max_cpus` tasks can run at the same moment, one task per CPU. A task cannot start before its scheduled time; if every CPU is busy at that time, it waits until a CPU becomes free.
Implement `last_finish_time(start_times, duration, max_cpus)`, which returns the time at which the last task finishes.
**Rules**
- `start_times[i]` is the scheduled start time of task `i`. Each task runs on one CPU, without interruption, for exactly `duration` time units: a task that starts at time `t` finishes at time `t + duration`.
- A CPU that finishes a task at time `t` can start another task at time `t`.
- A CPU never stays idle while a task whose scheduled time has arrived is waiting.
- Waiting tasks start in order of their scheduled start times. Because every task has the same duration, the order among tasks with equal scheduled times does not change the answer.
- Return the latest finish time over all tasks as a single integer.
**Example 1**
```text
Input: start_times = [1, 4, 6], duration = 5, max_cpus = 2
Output: 11
```
The task scheduled at 1 runs from 1 to 6 on one CPU, and the task scheduled at 4 runs from 4 to 9 on the other. At time 6 the first CPU is free again, so the third task runs from 6 to 11.
**Example 2**
```text
Input: start_times = [10, 0, 0, 0], duration = 3, max_cpus = 2
Output: 13
```
Two of the tasks scheduled at 0 run from 0 to 3; the third waits and runs from 3 to 6. The task scheduled at 10 finds a free CPU and runs from 10 to 13.
**Constraints**
- `1 <= len(start_times) <= 10^5`
- `0 <= start_times[i] <= 10^9`, integers, in no particular order (duplicates allowed)
- `1 <= duration <= 10^9`
- `1 <= max_cpus <= 10^5`
- The answer can reach about `10^14`, which is beyond 2^31 - 1 but below 2^53: use 64-bit integers (Java `long`, C++ `long long`). Start and finish times of queued tasks can exceed 2^31 - 1 as well.
Constraints
- 1 <= len(start_times) <= 10^5
- 0 <= start_times[i] <= 10^9, integers, in no particular order (duplicates allowed)
- 1 <= duration <= 10^9
- 1 <= max_cpus <= 10^5
- The answer can reach about 10^14, which is beyond 2^31 - 1 but below 2^53: use 64-bit integers (Java long, C++ long long).
Examples
Input: ([1, 4, 6], 5, 2)
Expected Output: 11
Explanation: Source Example 1: the first CPU frees at 6 exactly when the task scheduled at 6 arrives, so that task runs 6 to 11 (CPU reuse at time t).
Input: ([1, 4, 6], 5, 1)
Expected Output: 16
Explanation: Source Example 2: one CPU runs the tasks back to back, 1 to 6, 6 to 11 and 11 to 16.
Hints
- Tasks become eligible in order of their scheduled start times, not in the order the list gives them.
- When a task is due, what matters is the earliest moment some CPU becomes free; a CPU that frees at time t can take a task at time t.
- Queued start and finish times can exceed 2^31 - 1, so keep every time value in 64-bit integers.