Re: [閒聊] 每日LeetCode
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 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.簡單來講就是 維護一個時間 time，只要任務的到達時間比 time 小就加進 candidate
加完之後結算 candidate 最優先的那項(所需時間最小->編號最小)
執行他 也就是 time += 他的所需時間，然後用新的 time 去更新 candidate
2.所以 candidate 只需要知道最小(最優先)的是誰 -> 可以用 heap
要知道加進 candidate 的順序 -> tasks 可以先用到達時間 sort 一遍
這樣只要遇到 tasks[i] 的到達時間比 time 大就能先停 因為後面的也都加不進來
更新 time 之後再從 tasks[i] 開始檢查就好
3.如果目前的 time 完全沒有 candidate 就直接加速到現在最小的到達時間
Python code:
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
n = len(tasks)
for i in range(n):
tasks[i].append(i)
tasks.sort()
heap, res = [], []
time = 0
i = 0
while i < n or heap:
while i < n and tasks[i][0] <= time:
heapq.heappush(heap, (tasks[i][1], tasks[i][2]))
i += 1
if heap:
task = heapq.heappop(heap)
time += task[0]
res.append(task[1])
else:
time = tasks[i][0]
return res
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.79 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672298534.A.E22.html
推
12/29 15:25,
2年前
, 1F
12/29 15:25, 1F
→
12/29 15:26,
2年前
, 2F
12/29 15:26, 2F
推
12/29 15:38,
2年前
, 3F
12/29 15:38, 3F
→
12/29 15:38,
2年前
, 4F
12/29 15:38, 4F
推
12/29 15:41,
2年前
, 5F
12/29 15:41, 5F
→
12/29 15:45,
2年前
, 6F
12/29 15:45, 6F
推
12/29 16:01,
2年前
, 7F
12/29 16:01, 7F
推
12/30 01:14,
2年前
, 8F
12/30 01:14, 8F
→
12/30 01:17,
2年前
, 9F
12/30 01:17, 9F
→
12/30 01:36,
2年前
, 10F
12/30 01:36, 10F
討論串 (同標題文章)
