力扣1235.规划兼职工作
力扣1235.规划兼职工作
-
动态规划 + 二分
- 将所有工作按照结束时间排序
- f[i]表示前i个工作可获取的最大收益
- 状态转移：取第i个工作，f[i] = profit[i] + f[j]，其中j为结束时间小于i的开始时间的最大数
- 不取第i个工作，f[i] = f[i-1]
- 可以通过二分找到 j
- 优化：
-
class Solution { public: int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) { int n = startTime.size(); //三元组 vector<array<int,3>> jobs(n); for(int i=0;i<n;i++) jobs[i] = {endTime[i],startTime[i],profit[i]}; //按照结束时间排序 ranges::sort(jobs,[](auto &a,auto &b){return a[0] < b[0];}); vector<int> f(n+1); for(int i=0;i<n;i++) { //j = upper_bound() - jobs.begin() - 1 + 1; //以i的开始时间作为结束时间在jobs里二分 int j = upper_bound(jobs.begin(),jobs.begin()+i,array<int,3>{jobs[i][1],INT_MAX}) - jobs.begin(); f[i+1] = max(f[i],f[j] + jobs[i][2]); } return f[n]; } };