题目描述
这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
样例:
输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：
我们选出第 1 份和第 4 份工作，
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。
思路：
1 const int maxn=5e4+10; 2 struct node{ 3 int l,r,val; 4 bool operator<(const node &a)const { 5 return r<a.r; 6 } 7 }N[maxn]; 8 class Solution { 9 public: 10 int dp[maxn]; 11 int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) { 12 int len=startTime.size(); 13 for(int i=0;i<len;i++)N[i].l=startTime[i],N[i].r=endTime[i],N[i].val=profit[i]; 14 sort(N,N+len); 15 for(int i=0;i<len;i++){ 16 if(i==0)dp[i]=N[i].val; 17 else { 18 int l=0,r=i-1; 19 while(l<=r){ 20 int mid=(l+r)/2; 21 if(N[mid].r<=N[i].l)l=mid+1; 22 else r=mid-1; 23 } 24 l--; 25 if(l!=-1)dp[i]=max(dp[i-1],dp[l]+N[i].val); 26 else dp[i]=max(dp[i-1],N[i].val); 27 } 28 } 29 return dp[len-1]; 30 } 31 };
原文：https://www.cnblogs.com/ljy08163268/p/11716760.html
