Minimum Makespan for Hybrid CPU-GPU Pipeline
You are given a 2D integer array tasks where tasks[i] = [cpu_time, gpu_time] represents a task that must be executed in two sequential phases.
- A single shared CPU processes the first phase of each task. The CPU can only work on one task at a time, sequentially without interruption.
- Once the CPU completes the first phase of task
i, its second phase (GPU post-processing) starts immediately. The GPU phase runs independently, and multiple tasks can undergo GPU post-processing concurrently.
Find the optimal order to execute tasks on the CPU so that the overall completion time (makespan), defined as the time when all tasks finish their GPU post-processing, is minimized. Return this minimum completion time.
[ "[[2, 5], [1, 3], [4, 1]]" ]
Explanation. Sorting tasks by GPU time in descending order gives [2, 5], [1, 3], and [4, 1]. Task 1 finishes CPU at time 2 and GPU at time 7. Task 2 finishes CPU at time 3 and GPU at time 6. Task 3 finishes CPU at time 7 and GPU at time 8. The maximum completion time across all tasks is 8.
[ "[[3, 2], [2, 8], [5, 4]]" ]
Explanation. Sorting by GPU time descending yields [2, 8], [5, 4], and [3, 2]. CPU completion times are 2, 7, and 10. GPU completion times are 10, 11, and 12. The maximum completion time is 12.
[ "[[5, 10]]" ]
Explanation. With a single task, CPU finishes at time 5 and GPU finishes at time 5 + 10 = 15.
[ "[[1, 5], [1, 5], [1, 5]]" ]
Explanation. All tasks are identical. CPU finishes them at times 1, 2, and 3. GPU completion times are 6, 7, and 8. The max completion time is 8.
[ "[[10, 1], [1, 10]]" ]
Explanation. Processing task [1, 10] first finishes CPU at time 1 and GPU at time 11. Processing task [10, 1] second finishes CPU at time 11 and GPU at time 12. The maximum completion time is 12.
[ "[[4, 6], [2, 1], [3, 6], [1, 2]]" ]
Explanation. Sorting by GPU time descending gives tasks in order [4, 6], [3, 6], [1, 2], [2, 1]. CPU ends at 4, 7, 8, 10. GPU ends at 10, 13, 10, 11. Max completion time is 13.
Follow-up: What if there are multiple identical CPU cores available to execute the CPU pre-processing phase?
- `1 <= tasks.length <= 10^5` - `tasks[i].length == 2` - `1 <= tasks[i][0], tasks[i][1] <= 10^9`