Pythonでジョブをスケジュールして最大の利益を得るプログラム

各間隔に3つの値[開始、終了、利益]が含まれる間隔のリストがあるとします。一度に実行できるタスクは1つだけであり、得ることができる最大の利益を見つける必要があります。

したがって、入力がintervals =[[1、2、100]、[3、5、40]、[6、19、150]、[2、100、250]]のような場合、出力は350になります。これらの2つの間隔[1、2、100]と[2、100、250]をとることができるので

これを解決するために、次の手順に従います

• d：=値としてリストを含む空のマップ
• n：=0
• 間隔を置いて（開始、終了、利益）ごとに、
  • 終了>nの場合、
    • n：=終了
• ペア（開始、終了）をd[終了]に挿入します
• A：=サイズn+1のリストで0を入力
• 範囲0からAのサイズで終了する場合は、
  • 終了がdの場合、
    • d [end]の（開始、利益）ペアごとに、
      を実行します。
      • A [end]：=最大A [end]、（A [start] +利益）およびA [end-1]
  • それ以外の場合、
    • A [end]：=A [end-1]
• Aの最後の値を返す

例（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