Python程序：查找完成任务所需的最小时间（相同类型任务之间有k个时间间隔）

假设我们有一个名为tasks的整数列表，其中每个项目代表不同的任务类型，我们还有一个非负整数k。每个任务需要一个单位时间来完成，并且必须按正确的顺序完成任务，但我们必须在执行两个相同类型任务之间留出k个单位时间。在任何时候，我们可以执行任务或等待。我们必须找到完成所有任务所需的时间量。

因此，如果输入类似于tasks = [0, 1, 1, 2] k = 2，则输出将为6，因为前两个任务是不同类型的，因此可以无需任何间隔地执行它们，现在在时间2，下一个任务是相同类型的任务，我们必须等待2个时间槽，然后执行任务，最后是其他类型的任务，类型2。所以执行此任务。所以它就像[0, 1, 等待, 等待, 1, 2]。由此我们可以确定，我们需要6个时间槽。

为了解决这个问题，我们将遵循以下步骤：

  • tick := 0
  • slot := 新建一个映射
  • 对于tasks中的每个t，执行：
    • 如果t在slot中，则tf := slot[t]
    • 如果tf不为空并且tf - tick > 0，则
      • tick := tick + tf - tick
    • tick := tick + 1
    • slot[t] := tick + k
  • 返回tick

示例

让我们来看下面的实现，以便更好地理解：

def solve(tasks, k):
   tick = 0
   slot = {}
   for t in tasks:
      tf = slot.get(t)
      if tf is not None and tf - tick > 0:
         tick += tf - tick
      tick += 1
      slot[t] = tick + k

   return tick

tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k))

输入

[0, 1, 1, 2]

输出

6

更新于：2021年10月14日

345 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告