从算法到工程，从「单线程 CPU」算法题到「实现操作系统」

输入：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 并进入空闲状态

输入：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 并进入空闲状态

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;
    }
}