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

問題の概要

「tasks」という値のリストがあり、それぞれ異なる値は異なるタスクの種類を表しているとします。さらに、負でない整数 k も与えられます。各タスクの完了には1分かかりますが、同じ種類のタスクを2回実行する間には、少なくとも k 分の待ち時間を挿入しなければなりません。どの時点でも、タスクを実行することも待機することも可能です。このとき、すべてのタスクを完了させるのに必要な最小の時間を求めるのが目的です。

例として、入力が nums = [2, 2, 2, 3, 3, 2]、k = 1 の場合を考えてみましょう。このとき出力は 7 になります。最適な実行順序が [2, 3, 2, 3, 2, 待機, 2] となり、合計7つのスロット（各1分）ですべてのタスクが完了するためです。

解決アプローチ：貪欲法によるスケジューリング

この問題は貪欲法（グリーディ法）で効率的に解くことができます。ポイントは、「各ラウンド（k + 1 分）ごとに、残り数の多いタスクの種類から優先的に実行する」という戦略です。残数の多い種類を早めに消化しておくことで、後半に長い待機時間が発生するのを防ぎ、全体の所要時間を最小化できます。

アルゴリズムの手順

• c := nums 内の各値の出現回数を記録したカウンター
• ans := 0（経過時間）、lastsize := 0（直前ラウンド開始時のタスク種類数）
• c が空になるまで、次の処理を繰り返します。
  • lastsize := 現在の c のサイズ（残っているタスクの種類数）
  • c の中で最も出現回数の多い (k + 1) 種類の値 x それぞれに対して、次を行います。
    • c[x] := c[x] − 1（そのタスクを1件実行）
    • c[x] が 0 になった場合は、c からそのキーを削除する
  • ans := ans + (k + 1)（1ラウンド分の時間を加算）
• ans + lastsize − (k + 1) を返す

なぜ最終ラウンドの補正が必要なのか？

ループ内では毎回 k + 1 を加算していますが、実際の最終ラウンドでは残りのタスク数が k + 1 未満になる可能性があります。その場合、最後のタスク実行後の待機時間は不要なので、最終ラウンドの所要時間を「lastsize 分」に置き換える必要があります。これが ans + lastsize − (k + 1) という式の役割です。なお、最終ラウンド開始時の種類数が必ず k + 1 以下になるのは、それより多ければタスクが残り続け、ループが継続するためです。

Pythonでの実装例

以下が実際の実装コードです。collections.Counter を活用することで、各タスクの残数管理と「最も多い種類の抽出」を簡潔に記述できます。

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

計算量について

n をタスクの総数、m をタスクの種類数とすると、most_common(k + 1) はヒープ構造を利用して O(m log(k + 1)) で動作します。全体の計算量はほぼ O(n log m) 程度に収まるため、タスク数が多いケースでも効率的に動作するのが特徴です。