Posted on 2022-12-29 17:10
Uriel 閱讀(56)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構 、
閑來無事重切Leet Code
給出一系列任務，每個任務i需要在時刻tasks[i][0]之后才能開始運行，需要運行的時長為tasks[i][1]，問如果用一個單線程CPU運行這堆任務，應該怎樣安排先后順序
*如果兩個任務開始時間相同，則先運行耗時短的任務
先將所有任務按照開始時間排序，然后維護一個最小堆，初始時間為開始時間最早的任務的開始時間，然后把運行開始時間不晚于這個時刻的任務壓進heap，heap的排序依據為運行時間，同時保存各個任務的id。然后每次pop heap頂端的任務，更新現在的時刻為該任務的開始時間+需要運行的時間，再將符合這一更新后時間的任務壓進heap，直到處理完所有任務
用python的heapq實現
1 #1834
2 #Runtime: 1831 ms (Beats 94.44%)
3 #Memory: 64.2 MB (Beats 27.78%)
4
5 class Solution(object):
6 def getOrder(self, tasks):
7 """
8 :type tasks: List[List[int]]
9 :rtype: List[int]
10 """
11 ans = []
12 tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)])
13 i = 0
14 cur_time = tasks[0][0]
15 h = []
16 while len(ans) < len(tasks):
17 while i < len(tasks) and tasks[i][0] <= cur_time:
18 heapq.heappush(h, (tasks[i][1], tasks[i][2]))
19 i += 1
20 if h:
21 t, idx = heapq.heappop(h)
22 cur_time += t
23 ans.append(idx)
24 elif i < len(tasks):
25 cur_time = tasks[i][0]
26 return ans