Pythonで課題の割り当てから獲得できる最大クレジットを求めるプログラム

同じサイズの2つのリスト「deadlines」と「credits」があるとします。これらは講義の課題（アサインメント）を表しています。deadlines[i] は課題 i の締め切り日を、credits[i] はその課題を完了したときに得られるクレジットの量を示します。

1つの課題を完了するには1日かかり、締め切り日当日またはそれ以前であれば完了できます。ただし、複数の課題を同時にこなすことはできません。ここで、いくつかの課題を選んで完了することで得られるクレジットの合計の最大値を求める必要があります。

例として、deadlines = [1, 2, 2, 2]、credits = [4, 5, 6, 7] の場合、出力は 18 になります。これは、クレジット5の課題を0日目に、クレジット6の課題を1日目に、クレジット7の課題を2日目に完了することで、合計18のクレジットを獲得できるためです。

解決のためのアプローチ

この問題は貪欲法（グリーディ法）を用いて解くことができます。基本的な考え方は、「クレジットが大きい課題から優先的に、できるだけ締め切りギリギリの日へスケジュールする」というものです。こうすることで、他の課題のために早い日程を空けておくことができます。具体的には、以下の手順に従います。

• 締め切り日とクレジットをペアにしたリスト a を作成し、クレジットの降順でソートする
• a が空の場合は 0 を返す
• res := (締め切りの最大値 + 1) のサイズのリストを作成し、すべて 0 で初期化する（各日が使用済みかどうかのフラグ）
• ans := 0 とする
• a 内の各ペア (i, j) について、k を i から 0 まで減らしながら確認し、res[k] が 0 の場合は res[k] を 1 に設定し、ans に j を加算してループを抜ける
• 最後に ans を返す

理解を深めるために、以下の実装例を見てみましょう。

実装例

class Solution:
   def solve(self, deadlines, credits):
      a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
      if not a:
         return 0
      res = [0] * (max(deadlines) + 1)
      ans = 0
      for i, j in a:
         for k in range(i, -1, -1):
            if not res[k]:
               res[k] = 1
               ans += j
               break
      return ans
   
ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))

入力

[1, 2, 2, 2], [4, 5, 6, 7]

出力

18

計算量について

課題の数を n、締め切りの最大値を d とすると、ソートに O(n log n)、各課題に対して最大 d 日分の探索が発生するため、全体の時間計算量は O(n log n + n・d) となります。また、日付の使用状況を記録する配列が必要なため、空間計算量は O(d) です。課題数や締め切りの範囲が大きい場合は、Union-Find（素集合データ構造）などを用いて空き日の検索を高速化する方法もあります。