Posted on 2022-12-29 17:10
Uriel 阅读(47)
评论(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