Pythonでジョブスケジューリング問題を解き、最大の利益を求めるプログラム

問題の概要

各要素が [start（開始時刻）, end（終了時刻）, profit（利益）] の3つの値を持つ区間（ジョブ）のリストがあるとします。同時に実行できるタスクは1つだけという制約のもとで、得られる最大の利益を求めるのがこの問題の目的です。

例えば、入力が以下の場合を考えてみましょう。

intervals = [[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]]

この場合の出力は 350 になります。なぜなら、[1, 2, 100] と [2, 100, 250] の2つの区間を選ぶことで、100 + 250 = 350 という最大の利益が得られるからです。

解法のアプローチ：動的計画法（DP）

この問題は、各時刻ごとに「その時点までに得られる最大利益」を記録していく動的計画法によって効率的に解くことができます。手順は以下の通りです。

• d := 値としてリストを格納する空のマップ（辞書）を用意する
• n := 0 で初期化する
• intervals 内の各 (start, end, profit) について処理を行う
  • end > n であれば、n := end と更新する
  • ペア (start, profit) を d[end] に追加する
• A := サイズ n + 1 のリストを作成し、すべて 0 で初期化する
• end を 0 から A のサイズまで順に処理する
  • end が d に存在する場合
    • d[end] 内の各 (start, profit) ペアについて、A[end] := max(A[end], A[start] + profit, A[end - 1]) と更新する
  • それ以外の場合
    • A[end] := A[end - 1] とする
• 最後に A の末尾の値を返す

ここでのポイントは、あるジョブが時刻 end に終わる場合、「そのジョブを実行しない場合の利益（A[end - 1]）」と「そのジョブを実行した場合の利益（開始時刻 start までの最大利益 A[start] ＋ このジョブの利益）」を比較して、大きい方を採用することです。これにより、時間的に重ならないジョブの組み合わせの中から最適な選択が保証されます。

Pythonでの実装例

それでは、上記のアルゴリズムをPythonで実装してみましょう。

from collections import defaultdict
class Solution:
   def solve(self, intervals):
      d = defaultdict(list)
      n = 0
      for start, end, profit in intervals:
         if end > n:
            n = end
         d[end].append([start, profit])
      A = [0 for i in range(n + 1)]
      for end in range(len(A)):
         if end in d:
            for start, profit in d[end]:
               A[end] = max(A[end], A[start] + profit, A[end - 1])
         else:
            A[end] = A[end - 1]
      return A[-1]
ob = Solution()
intervals = [[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]
print(ob.solve(intervals))

入力

[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]

出力

350

まとめ

このように、終了時刻をキーにしてジョブを整理し、DPテーブルを使って各時点での最大利益を累積的に更新していくことで、重複のないジョブ選択における最大利益を効率よく求めることができます。計算量は O(n + ジョブ数) 程度に抑えられ、ジョブスケジューリング問題の典型的な解法として覚えておくと役立ちます。