Re: [閒聊] 每日LeetCode
※ 引述《pandix (麵包屌)》之銘言：
: ※ 引述《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
https://pastebin.com/HAcPWLDf
經過多次debug之後好不容易提交成功
只有我寫得這麼爛嗎
哭啊
--
(づ′・ω・）づ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.241.148.89 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672328851.A.6AD.html
→
12/29 23:54,
2年前
, 1F
12/29 23:54, 1F
→
12/29 23:54,
2年前
, 2F
12/29 23:54, 2F
推
12/30 01:16,
2年前
, 3F
12/30 01:16, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 163 之 719 篇)：