【算法题】1834. 单线程 CPU

插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。
坚持不懈，越努力越幸运，大家一起学习鸭~~~

题目：

给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。

现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：

如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
CPU 可以在完成一项任务后，立即开始执行一项新任务。
返回 CPU 处理任务的顺序。

示例 1：

输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
输出：[0,2,3,1]
解释：事件按下述流程运行：

• time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
• 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
• time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
• time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
• 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
• time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
• time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
• time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
• time = 10 ，CPU 完成任务 1 并进入空闲状态
  示例 2：

输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出：[4,3,2,0,1]
解释：事件按下述流程运行：

• time = 7 ，所有任务同时进入任务队列，可执行任务项 = {0,1,2,3,4}
• 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
• time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
• time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
• time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
• time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
• time = 40 ，CPU 完成任务 1 并进入空闲状态

提示：

tasks.length == n
1 <= n <= 10^5
1 <= enqueueTimei, processingTimei <= 10^9

java代码：

class Solution {public int[] getOrder(int[][] ts) {int n = ts.length;// 将 ts 转存成 nts，保留任务编号int[][] nts = new int[n][3];for (int i = 0; i < n; i++) nts[i] = new int[]{ts[i][0], ts[i][1], i};// 根据任务入队时间进行排序Arrays.sort(nts, (a,b)->a[0]-b[0]);// 根据题意，先按照「持续时间」排序，再根据「任务编号」排序PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{if (a[1] != b[1]) return a[1] - b[1];return a[2] - b[2];});int[] ans = new int[n];for (int time = 1, j = 0, idx = 0; idx < n; ) {// 如果当前任务可以添加到「队列」中（满足入队时间）则进行入队while (j < n && nts[j][0] <= time) q.add(nts[j++]);if (q.isEmpty()) {// 如果当前「队列」没有任务，直接跳到下个任务的入队时间time = nts[j][0];} else {// 如果有可执行任务的话，根据优先级将任务出队（记录下标），并跳到该任务完成时间点int[] cur = q.poll();ans[idx++] = cur[2];time += cur[1];}}return ans;}
}