Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一系列任务,每个任务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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理