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