力扣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];}};