间隔期最大利润

Question

我们得把车租给顾客。我们有一个列表，它的每一个元素代表给出汽车的时间，第二个->表示归还汽车的时间，第三个->表示在贷款中获得的利润。所以我需要找出能赚到的最大利润。

例：

( [1,2,20], [3,6,15], [2,8,25], [7,12,18], [13,31,22] )

最大利润是75英镑。1,2 + 3,6 + 7,12 + 13,31

我们可以有重叠的间隔。我们需要选择这样的情况，使我们的利润最大化。

Answer 1

使用类似于动态编程的方法。第一次用第一个元素排序。您有2行，如果使用此时间，则第一次显示赢得的最多，如果不使用，则另一次显示为大多数赢得。然后你会把每一项任务放在相关的时间里，并在每一段时间里看到拥有或不拥有它是一个不错的选择。

注意，如果间隔是合法的，我们会选择所有的。