給出一系列任務(wù)，每個(gè)任務(wù)i需要在時(shí)刻tasks[i][0]之后才能開始運(yùn)行，需要運(yùn)行的時(shí)長為tasks[i][1]，問如果用一個(gè)單線程CPU運(yùn)行這堆任務(wù)，應(yīng)該怎樣安排先后順序
*如果兩個(gè)任務(wù)開始時(shí)間相同，則先運(yùn)行耗時(shí)短的任務(wù)
先將所有任務(wù)按照開始時(shí)間排序，然后維護(hù)一個(gè)最小堆，初始時(shí)間為開始時(shí)間最早的任務(wù)的開始時(shí)間，然后把運(yùn)行開始時(shí)間不晚于這個(gè)時(shí)刻的任務(wù)壓進(jìn)heap，heap的排序依據(jù)為運(yùn)行時(shí)間，同時(shí)保存各個(gè)任務(wù)的id。然后每次pop heap頂端的任務(wù)，更新現(xiàn)在的時(shí)刻為該任務(wù)的開始時(shí)間+需要運(yùn)行的時(shí)間，再將符合這一更新后時(shí)間的任務(wù)壓進(jìn)heap，直到處理完所有任務(wù)
用python的heapq實(shí)現(xiàn)
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