Re: [閒聊] 每日LeetCode

1834. Single-Threaded CPU 給你一個陣列tasks，其中tasks[i][0]表示到達CPU的時間tasks[i][1]表示處理所需時間 ，CPU要處理一系列的任務，根據以下的優先順序： 1.最早到達CPU的任務優先 2.同時間到達時處理所需時間最小的優先 3.處理時間相同時任務編號i較小的優先 我們需要找出CPU執行所有任務的執行順序。 註：CPU沒任務可以處理的時候會idle，直到下個任務到達 Example： Input: tasks = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1] Explanation: - At time 1 tasks[0] 到達了，CPU={0} CPU處理完了tasks[0]，time=1+2=3 - At time 3 tasks[1]和tasks[2]到達了，CPU={1,2} 因為task[2]有較小的處理時間所以CPU先處理他，time=3+2=5 - At time 5 task[3]到達了，CPU={1,3} 因為task[3]有較小的處理時間所以CPU先處理他，time=5+1=6 - At time 6 CPU處理最後一個任務task[1] 依照上面的順序，我們要返回[0,2,3,1] 思路： 1.因為還要照索引順序處理很麻煩，我先用一個heap依照到達時間、處理時間 排序task，並且一併記錄當前任務的索引。 2.用另外一個heap來表示當前CPU可以處理的任務，並且按照處理時間、索引 排序來讓每次從heap裡面取出任務處理時都是最佳選擇。 3.第一步的heap是heap1，第二步的是heap2，我們先把第一個任務（heap1.top） 加入heap2，如果當前CPU是idle，則直接令時間為heap最頂層： heap2.offer(heap1.poll()); while (!heap2.isEmpty()) { int[] curr = heap2.poll(); if (time < curr[0]) { time = curr[0]; } } 4.CPU開始處理當前任務: time += curr[1]; res[k++] = curr[2]; 5.檢查做完任務後，哪些任務也到達CPU了，若heap1存在小於time的task通通 都加到heap2。 while (!heap1.isEmpty() && time >= heap1.peek()[0]) { heap2.offer(heap1.poll()); } 6.這邊有個corner case，如果第五步找不到任務CPU進入idle迴圈會結束，所以 heap2如果沒任務但heap1有的時候要從heap1拉一個任務。 if (heap2.isEmpty() && !heap1.isEmpty()) { heap2.offer(heap1.poll()); } Java Code： ---------------------------------------- class Solution { public int[] getOrder(int[][] tasks) { int n = tasks.length; int[] res = new int[n]; PriorityQueue<int[]> heap1 = new PriorityQueue<>((o1, o2) -> { int cmp = o1[0] - o2[0]; return (cmp != 0) ? cmp : o1[1] - o2[1]; }); for (int i = 0; i < n; i++) { heap1.offer(new int[]{tasks[i][0], tasks[i][1], i}); } PriorityQueue<int[]> heap2 = new PriorityQueue<>((o1, o2) ->{ int cmp = o1[1] - o2[1]; return (cmp != 0) ? cmp : o1[2] - o2[2]; }); int k = 0; int time = 0; heap2.offer(heap1.poll()); while (!heap2.isEmpty()) { int[] curr = heap2.poll(); if (time < curr[0]) { time = curr[0]; } time += curr[1]; res[k++] = curr[2]; while (!heap1.isEmpty() && time >= heap1.peek()[0]) { heap2.offer(heap1.poll()); } if (heap2.isEmpty() && !heap1.isEmpty()) { heap2.offer(heap1.poll()); } } return res; } } ---------------------------------------- 最終版本 https://i.imgur.com/ovTs9Lr.png 好囉唆= = -- https://i.imgur.com/tdaniED.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 1.160.106.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672281499.A.D1D.html

→ sustainer123: 大師 12/29 10:38