Python 中调度任务以最少时间完成的程序

假设我们有一个名为 tasks 的值列表，其中每个不同的值代表一种不同的任务类型，我们还有一个非负整数 k。每个任务需要一分钟才能完成，但我们必须在执行两次相同类型任务之间等待 k 分钟。在任何时候，我们都可以执行任务或等待。我们必须找到完成所有任务所需的最短时间。

因此，如果输入类似于 nums = [2, 2, 2, 3, 3, 2]，k = 1，则输出将为 7，因为最佳排序为 [2, 3, 2, 3, 2, WAITING, 2]。

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

  • c := nums 中所有值的计数

  • ans := 0，lastsize := 0

  • 当 c 不为零时，执行以下操作

    • lastsize := c 的大小

    • 对于 c 中最常见的 (k + 1) 个值中的每个值 x，执行以下操作

      • c[x] := c[x] - 1

        • 如果 c[x] 等于 0，则

          • 移除 c[x]

    • ans := ans + k + 1

  • 返回 ans + lastsize - (k + 1)

让我们看看以下实现以获得更好的理解：

示例

 实时演示

class Solution:
   def solve(self, nums, k):
      from collections import Counter
      c = Counter(nums)
      ans = 0
      lastsize = 0
      while c:
         lastsize = len(c)
         for x, _ in c.most_common(k + 1):
            c[x] -= 1
            if c[x] == 0:
               del c[x]
         ans += k + 1
      return ans + lastsize - (k + 1)
ob1 = Solution()
nums = [2, 2, 2, 3, 3, 2]
k = 1
print(ob1.solve(nums, k))

输入

[2, 2, 2, 3, 3, 2], 1

输出

7

更新于: 2020年10月21日

181 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告