Python作業排程最大利潤程式

假設我們有一組區間，每個區間包含三個值[開始時間，結束時間，利潤]。我們一次只能執行一項任務，我們需要找到可以獲得的最大利潤。

因此，如果輸入類似於intervals = [[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]，則輸出將為350，因為我們可以選擇這兩個區間[1, 2, 100]和[2, 100, 250]

為了解決這個問題，我們將遵循以下步驟

d := 一個空對映，其值包含列表
n := 0
對於intervals中的每個(start, end, profit)，執行：
- 如果end > n，則
  - n := end
將(start, end)對插入d[end]
A := 一個大小為n + 1的列表，並用0填充
對於範圍從0到A大小的end，執行：
- 如果end在d中，則
  - 對於d[end]中的每個(start, profit)對，執行：
    - A[end] := A[end]，(A[start] + profit)和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]]

輸出

Arnab Chakraborty

更新於：2020年12月12日

762 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習