Q1834SingleThreadedCPU
簡介
給你一個二維陣列 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 并進入空閑狀態
鏈接：https://leetcode.cn/problems/single-threaded-cpu
解題思路
像這種題目描述很多的首先考慮進行模擬，題目大意是當CPU運行到一個時刻time時，對此時等待的所有任務進行排序，優先處理運行時間最短且序號最靠前的，這個排序程序可以使用優先佇列實作，對處理時間和序號進行排序，題目給的任務是沒有序號的，需要手動添加，同時給的任務是無序的，在處理之前需要根據開始時間進行排序，方便時間計算，
流程
- 首先時間time初始化為第一個任務開始的時間
- 將所有小于等于此時間的任務放到優先佇列中
- 取隊頭任務進行處理，time加上任務時間作為下一次添加任務的時間，當前序號放入回傳值里
- 重復以上步驟，注意當佇列為空時可以將時間置為下一個任務的開始時間（快進）
代碼
public class Q1834SingleThreadedCPU {
public int[] getOrder(int[][] tasks) {
int[][] taskArray = new int[tasks.length][3];
for (int i = 0; i < tasks.length; i++) { //對任務進行加工處理
taskArray[i][0] = tasks[i][0];
taskArray[i][1] = tasks[i][1];
taskArray[i][2] = i;
}
Arrays.sort(taskArray, Comparator.comparingInt(o -> o[0]));
PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> {
if (o1[1] == o2[1]){
return o1[2] - o2[2];
}
return o1[1] - o2[1];
}));
int[] rtn = new int[tasks.length];
int index = 0;
int time = taskArray[0][0]; //初始化時間為第一個任務開始時間
int i = 0;
while (i < taskArray.length) {
while (i < taskArray.length && taskArray[i][0] <= time){
queue.offer(taskArray[i]);
i++;
}
if (queue.isEmpty()){ //佇列為空時的處理
time = taskArray[i][0];
} else {
rtn[index++] = queue.peek()[2];
time += queue.peek()[1]; //時間跳到任務結束
queue.poll();
}
}
while (!queue.isEmpty()){
rtn[index++] = queue.peek()[2];
queue.poll();
}
return rtn;
}
}
要點
有一些坑要注意
- 當兩個任務處理時間相同時，優先序號小的，由于任務表是無序的，所以序號和任務開始時間并不等同
- 佇列為空時時間也要繼續前進，可以考慮快進到下一個任務開始時間
- 當對任務表遍歷完之后佇列仍然有值的處理
提交結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502004.html
標籤：其他