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]]

输出

350

更新于：2020年12月12日

762 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告
© . All rights reserved.