标签：LeetCode1235 max profit List int startTime 兼职 endTime 规划
LeetCode1235 规划兼职工作
- 按照结束时间进行排序
- \(f[i]\)表示前\(i\)个工作的最大报酬, 第\(i\)个工作可选可不选
- 第\(i\)个不拿: \(f[i] = max(f[i], f[i - 1])\)
- 第\(i\)个拿: \(f[i] = max(f[i], f[j] + profit[i])\), 其中\(j\)表示满足\(starTime[i] \ge endTime[j]\)最右的\(j\), 可以通过在排序的\(endTime\)数组中二分求解.
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
a, n = [], len(startTime)
for i in range(n): a.append((endTime[i], startTime[i], profit[i]))
a.sort(), endTime.sort()
f = [0] * n
f[0] = a[0][2]
for i in range(1, n):
index = bisect_right(endTime, a[i][1]) - 1
f[i] = max(f[i - 1], f[index] + a[i][2])
return f[-1]
标签：LeetCode1235,
max,
profit,
List,
int,
startTime,
兼职,
endTime,
规划
From： https://www.cnblogs.com/solvit/p/16721347.html