在Python中安排任务以获取最大利润的程序

假设我们有一个区间列表，每个区间包含三个值[start，end，profit]。我们一次只能执行一个任务，我们必须找到最大的利润。

因此，如果输入为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
• 在d[end]中插入（start，end）对
• A：大小为n + 1的列表，并用0填充
• 对于范围为0到A大小的end，进行以下操作
  • 如果end在d中，则
    • 对于d[end]中的每个(start，profit)对，执行以下操作
    • 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