Minimize the Finish Time of Tasks on Four-Core Processors
Company: JPMorgan Chase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Minimize the Finish Time of Tasks on Four-Core Processors
There are `n` processors, each with exactly four cores. Processor `i` becomes available at time `processorTime[i]`. You are also given `tasks`, where `tasks[j]` is the duration of task `j`.
There are exactly `4 * n` tasks. Assign each task to a unique core, and use each core only once. A task on processor `i` may start when that processor becomes available, so starting it immediately gives completion time `processorTime[i] + tasks[j]`. The four cores of a processor can work in parallel.
Return the minimum possible time at which all tasks have finished.
### Examples
**Example 1**
```text
Input: processorTime = [9,0], tasks = [9,8,7,6,5,4,3,2]
Output: 14
```
Give durations `[9,8,7,6]` to the processor available at time `0`; it finishes at `9`. Give `[5,4,3,2]` to the processor available at time `9`; it finishes at `14`. Finishing by time `13` is impossible: that later processor would need four tasks of duration at most `4`, but only three such tasks exist.
**Example 2**
```text
Input: processorTime = [3], tasks = [2,9,4,1]
Output: 12
```
All four tasks must use the only processor. Their completion times are `5`, `12`, `7`, and `4`, so the final completion time is `12`.
### Constraints
- `1 <= n == processorTime.length <= 25000`.
- `1 <= tasks.length <= 10^5`.
- `0 <= processorTime[i] <= 10^9`.
- `1 <= tasks[i] <= 10^9`.
- `tasks.length == 4 * n`.
### Clarifying Questions
- Are the four tasks on a processor executed sequentially? No; its four cores can execute them in parallel once the processor is available.
- Can a core process a second task after finishing its first? No; each core is used only once.
- May tasks be assigned to processors in a different order from the input? Yes; choose any assignment while respecting the core counts.
- Do equal durations or equal availability times represent fewer tasks or cores? No; each listed task and each processor still has its own identity and capacity.
- Does starting a task later help? No; delaying a start cannot make its finish time earlier. Starting at availability is sufficient when minimizing the final completion time.
### C++ Interface
```cpp
class Solution {
public:
int minProcessingTime(vector<int>& processorTime, vector<int>& tasks) {
}
};
```
### Reasoning Checkpoints
- Model the four-core capacity and one-use-per-core rule accurately.
- Justify why the proposed assignment minimizes the last completion time.
- Account for all tasks, repeated values, zero availability times, and the maximum possible finish time.
```hint Exchange two task assignments
Consider an earlier available core and a later available core. If the later core has the longer of their two tasks, can swapping those tasks increase the maximum of the two finish times? Treat each processor as four cores with equal availability.
```
Overview: Assign tasks to processors with four single-use cores and different availability times, minimizing the time at which every task has finished.