题目内容

一台单核 CPU 上要调度 $n$ 个任务。第 $i$ 个任务（下标从 $0$ 开始）由三个数组给出：

• arrival[i]：到达时刻（从此刻起才可被调度）
• duration[i]：需要占用 CPU 的总时长（可被打断，剩余时间累加到凑满为止）
• priority[i]：优先级，数值越大优先级越高

时间按整数时刻推进。调度规则（可抢占）：

1. 任意时刻，在所有「已到达且尚未完成」的任务中，选优先级最高者占用 CPU；优先级相同则选下标更小者。
2. 若正在运行时有更高优先级任务到达，立即抢占；被抢占任务保留剩余时长，之后可再跑。
3. 某任务的完成时间是其剩余时长首次变为 $0$ 的时刻。

请返回长度为 $n$ 的数组，ans[i] 为任务 $i$ 的完成时间。

请实现：

finishTimes(arrival: int[], duration: int[], priority: int[]) -> int[]

输入描述

三行整数数组：arrival、duration、priority，长度均为 $n$。

约束：

• $1 \le n \le 10^4$
• $0 \le \texttt{arrival}[i] \le 10^9$
• $1 \le \texttt{duration}[i] \le 10^4$
• $1 \le \texttt{priority}[i] \le 10^9$

输出描述

一行整数数组，形如 [4, 2, 6]（元素间逗号后有一个空格）。

样例1

输入：

[0, 1, 2]
[3, 1, 2]
[1, 2, 1]

输出：

[4, 2, 6]

说明：

• 时刻 $[0,1)$：只有任务 $0$，跑 $1$ 单位，剩余 $2$
• 时刻 $[1,2)$：任务 $1$ 到达且优先级更高，抢占；任务 $1$ 于时刻 $2$ 完成
• 时刻 $[2,4)$：任务 $2$ 与任务 $0$ 优先级同为 $1$，选下标更小的 $0$，跑完剩余 $2$，于时刻 $4$ 完成
• 时刻 $[4,6)$：跑任务 $2$，于时刻 $6$ 完成

故完成时间为 [4, 2, 6]。

样例2

输入：

[0]
[5]
[1]

输出：

[5]

说明：唯一任务从 $0$ 跑到 $5$，完成时间为 $5$。