Pythonで最短時間でタスクをスケジュールするプログラム

タスクと呼ばれる値のリストがあり、それぞれの異なる値が異なるタスクタイプを表し、負でない整数kもあるとします。各タスクは1分で完了しますが、同じタイプの2つのタスクを実行するまでにk分待つ必要があります。いつでも、タスクを実行したり、待機したりできます。すべてのタスクを完了するのにかかる最小の時間を見つける必要があります。

したがって、入力がnums =[2、2、2、3、3、2]、k =1の場合、最適な順序は[2、3、2、3、2]であるため、出力は7になります。待っています、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