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


--

蛤?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.79 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672298534.A.E22.html
推 Rushia: 大師
→ SecondRun: 今天題目太囉嗦了==寫了發現根本誤解 氣死
推 NTHUlagka: 大師 leetcode幫人也變得太多了吧 好扯乾脆大家開個DC
→ NTHUlagka: 一起刷題算了
推 SecondRun: 好 ++
→ pandix: @leetcode幫幫主Rushia
推 NTHUlagka: ++
推 AyuniD: ++
→ AyuniD: 跟我的想法差不多，但我不是用 heap
→ AyuniD: 試了一下只快一點點，哭啊