我正在处理一个进程管理问题。假设有一系列需要按顺序完成的工作,每个项目都必须在进行工作2之前先完成工作1。请看以下示例:
work1 8 6 2 4
work2 3 1 3 12
我们需要用8小时完成第一列的工作1,还需要3个小时,但如果我们先完成第4列,在接下来的12小时内,我们有时间做第3列和第2列。最好将这一列放在第一步。
我的直觉是,工作2是瓶颈,也就是说,我们至少需要使用3+1+3+12=20个小时来完成这笔交易。也就是说,始终让工作2的流程尽可能忙碌。我的算法:反向排序工作2并排序工作1,因为我们希望保持工作2流程尽可能忙碌。
这是我的算法,看起来很有效:
class Solution(object):
def least_time(self, intervals):
intervals.sort(key = lambda x: (-x[1], x[0]))
time1 = time2 = 0
print intervals
for inv in intervals:
item1, item2 = inv
if time1 + item1 <= time2 + item2:
time1 += item1
time2 += item2
else:
time1 += item1
time2 = time1 + item2
return time2
if __name__ == "__main__":
s = Solution()
invs = [(8,3), (6,1), (2,3), (4,12)]
print(s.least_time(invs))
>>>[(4, 12), (2, 3), (8, 3), (6, 1)]
>>>21
它能在21小时内按以上顺序完成任务。
我的问题是: 1. 我的算法正确吗? 2. 如何将此问题扩展到n个任务?(任务1 -> 任务2 -> 任务3 -> ...-> 任务n)
work1
任务,处理器2只能处理work2
任务吗? - slider