力扣 901. 股票价格跨度

思路

可以转化为背包问题

dp[i]表示做到第i份工作后的最大利益

因此在面对第i件工作时有两种情况

1. 不做第i件工作：dp[i] = dp[i - 1]
2. 做第i件工作，利益承接和第i件工作不冲突的dp：dp[i] = dp[k] + profit[i]
   1. 查找和第i件不冲突的工作k: bisect_right(data, starttime[i], hi=i, key=endtime[i])
   2. 完成第k件工作，还可以完成第i件工作

综合上述情况 dp[i] = max(dp[i - 1], dp[k] + profit[i])

解法

def jobScheduling(startTime, endTime, profit):
    # 背包问题 + 二分查找
    n = len(profit)
    dp = [0 for _ in range(n + 1)]
    data = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    for i in range(1, n + 1):
        k = bisect_right(data, data[i - 1][0], hi=i, key=lambda x: x[1])
        dp[i] = max(dp[i - 1], data[i - 1][-1] + dp[k])
    return dp[-1]