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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告