Split Tasks Into Contiguous Server Blocks to Maximize the Total of Top-m Times
Company: Arista Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A batch of tasks has to be split among servers. The tasks are in a fixed order, and task `i` takes `process_time[i]` time units. Each server receives one contiguous block of tasks, must receive at least `m` tasks, and runs its tasks sequentially. For this problem, a server's execution time is defined as the sum of the `m` largest processing times in its block. Split the tasks so that the total execution time over all servers is as large as possible, and return that maximum total.
The report did not give input sizes or value ranges; the constraints below fix them for practice.
### Function Signature
```python
def max_total_processing_time(process_time: list[int], num_servers: int, m: int) -> int:
```
### Rules
- The blocks partition the task list: every task goes to exactly one server, each of the `num_servers` servers receives exactly one contiguous block, and the blocks follow the task order.
- Every block contains at least `m` tasks.
- A block's execution time is the sum of its `m` largest values, counted per task rather than per distinct value: for the block `[5, 5, 1]` with `m = 2` it is `10`.
- Return the maximum, over all valid splits, of the sum of the blocks' execution times.
### Constraints
- `1 <= num_servers` and `1 <= m`
- `m * num_servers <= len(process_time) <= 2 * 10^5`, so at least one valid split exists.
- `1 <= process_time[i] <= 10^9`
- The answer can reach `2 * 10^14`, beyond the 32-bit signed maximum `2^31 - 1`, so use 64-bit integers. It stays well below `2^53`.
### Examples
**Example 1**
```text
Input: process_time = [3, 1, 4, 1, 5, 9, 2, 6], num_servers = 2, m = 2
Output: 24
```
Split into `[3, 1, 4, 1, 5]` and `[9, 2, 6]`. The first block's time is `5 + 4 = 9` and the second's is `9 + 6 = 15`, for a total of `24`. No split does better.
**Example 2**
```text
Input: process_time = [7, 2, 7, 1], num_servers = 3, m = 1
Output: 16
```
The split `[7]`, `[2]`, `[7, 1]` gives `7 + 2 + 7 = 16`. The split `[7, 2]`, `[7]`, `[1]` gives only `7 + 7 + 1 = 15`.
**Example 3**
```text
Input: process_time = [4, 8, 1, 2], num_servers = 2, m = 2
Output: 15
```
With exactly `m * num_servers` tasks, the only valid split is `[4, 8]` and `[1, 2]`, which gives `12 + 3 = 15`.
Overview: A coding problem about assigning an ordered list of tasks to servers in contiguous blocks of at least m tasks, where a server's time is the sum of the m largest task times in its block. It asks for the maximum possible total over all servers and tests reasoning about optimal splits and large sums.
Read the full Arista Networks Software Engineer interview experience this question came from
A batch of tasks has to be split among `num_servers` servers. The tasks are in a fixed order, and task `i` takes `process_time[i]` time units. Each server receives one contiguous block of tasks, must receive at least `m` tasks, and runs its tasks sequentially. For this problem, a server's execution time is defined as the sum of the `m` largest processing times in its block. Split the tasks so that the total execution time over all servers is as large as possible, and return that maximum total.
### Rules
- The blocks partition the task list: every task goes to exactly one server, each of the `num_servers` servers receives exactly one contiguous block, and the blocks follow the task order.
- Every block contains at least `m` tasks.
- A block's execution time is the sum of its `m` largest values, counted per task rather than per distinct value: for the block `[5, 5, 1]` with `m = 2` it is `10`.
- Return the maximum, over all valid splits, of the sum of the blocks' execution times.
### Example 1
```text
Input: process_time = [3, 1, 4, 1, 5, 9, 2, 6], num_servers = 2, m = 2
Output: 24
```
Split into `[3, 1, 4, 1, 5]` and `[9, 2, 6]`. The first block's time is `5 + 4 = 9` and the second's is `9 + 6 = 15`, for a total of `24`. No split does better.
### Example 2
```text
Input: process_time = [7, 2, 7, 1], num_servers = 3, m = 1
Output: 16
```
The split `[7]`, `[2]`, `[7, 1]` gives `7 + 2 + 7 = 16`. The split `[7, 2]`, `[7]`, `[1]` gives only `7 + 7 + 1 = 15`.
### Constraints
- `1 <= num_servers` and `1 <= m`
- `m * num_servers <= len(process_time) <= 2 * 10^5`, so at least one valid split exists.
- `1 <= process_time[i] <= 10^9`
- The answer can reach `2 * 10^14`, which exceeds the 32-bit signed maximum `2^31 - 1`: return a 64-bit integer (`long` in Java, `long long` in C++). It stays well below `2^53`.
Constraints
- 1 <= num_servers and 1 <= m
- m * num_servers <= len(process_time) <= 2 * 10^5, so at least one valid split exists
- 1 <= process_time[i] <= 10^9
- The answer can reach 2 * 10^14, which exceeds 2^31 - 1: return a 64-bit integer (long in Java, long long in C++); it stays well below 2^53
Examples
Input: ([3, 1, 4, 1, 5, 9, 2, 6], 2, 2)
Expected Output: 24
Explanation: Source example 1: blocks [3, 1, 4, 1, 5] (9) and [9, 2, 6] (15) give 24, the sum of the 4 largest values 9, 6, 5, 4.
Input: ([7, 2, 7, 1], 3, 1)
Expected Output: 16
Explanation: Source example 2: [7], [2], [7, 1] gives 7 + 2 + 7 = 16; [7, 2], [7], [1] gives only 15.
Hints
- Each block contributes exactly m task values to the total, and no task belongs to two blocks. How many task values make up the total in every valid split?
- Try bounding any split's total by ignoring where the block boundaries fall, then ask whether some split always reaches that bound.
- Duplicates count per task: in the block [5, 5, 1] with m = 2, both 5s count.