这是使用动态规划的加权作业(job)调度问题
How each list is structured = [city, start_day, end_day, revenue]
rev = [['A', 1, 7, 5], ['B', 6, 9, 4], ['C', 1, 5, 3]]
>>> print(max_rev(rec))
['B', 6, 9, 4], ['C', 1, 5, 3]
我对n log n的try :
- 使用修改后的合并排序(n log n)，根据城市的最后一天对列表进行排序，这将得到
[['C', 1, 5, 3], ['A', 1, 7, 5], ['B', 6, 9, 4]]个数字0->；n根据它现在的索引(我之前提到过插入排序，我搞砸了，因为它最糟糕的情况是n^2，所以我现在使用合并排序) - *clueless from here.创建一个
memo list of n (3) size，每个memo的指数代表一个特定城市在现在已排序版本中的指数位置 - 备忘录的每个索引都将包含销售人员在该城市工作所能获得的最大收入.通过循环浏览已排序的列表来实现这一点，对于每个城市信息，将其与开始日大于所选城市结束日的城市之间的所有收入相加.
`
import math
def max_rev(rev):
merge_sort(rev)
memo = [math.inf] * len(rev)
for i in range(len(rev)):
# another for loop would mean a n^2
return rev
rev = [['A', 1, 7, 5], ['B', 6, 9, 4], ['C', 1, 5, 3]]
print(max_rev(rev))
下面是我起草的另一个例子:
rev = [['A', 1, 7, 5], ['B', 6, 9, 4], ['C', 1, 5, 3],
['D', 2, 3, 5], ['E', 5, 7, 4], ['F', 4, 6, 3]]
output -> ['D', 2, 3, 5], ['B', 6, 9, 4]
谢谢