1.题目基本信息
1.1.题目描述
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
1.2.题目地址
https://leetcode.cn/problems/maximum-profit-in-job-scheduling/description/
2.解题方法
2.1.解题思路
动态规划+二分查找
2.2.解题步骤
第一步，状态定义；dp[i]为前i个兼职工作的最大报酬
第二步，状态转移；dp[i]=max(dp[i-1],dp[k]+profit[i-1]) （profit[i-1]为第i个工作的报酬；假设从0到i-2工作中，最后一个endTime小于等于i-1工作的startTime的工作下标为j，则k=j+1）。这里使用左闭右闭的未标记区间的方式进行二分
3.解题代码
Python代码
class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:length=len(startTime)jobs=sorted(zip(startTime,endTime,profit),key=lambda item:item[1])# 第一步，状态定义；dp[i]为前i个兼职工作的最大报酬dp=[0]*(length+1)# 第二步，状态转移；dp[i]=max(dp[i-1],dp[k]+profit[i-1]) （profit[i-1]为第i个工作的报酬；假设从0到i-2工作中，最后一个endTime小于等于i-1工作的startTime的工作下标为j，则k=j+1）。这里使用左闭右闭的未标记区间的方式进行二分for i in range(1,length+1):left,right=0,i-2 # 左闭右闭while left<=right:mid=(right-left)//2+leftif jobs[mid][1]<=jobs[i-1][0]:left=mid+1else:right=mid-1k=left # right+1dp[i]=max(dp[i-1],dp[k]+jobs[i-1][2])return dp[-1]
C++代码
class Solution {
public:int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {int length=startTime.size();vector<vector<int>> jobs(length);for(int i=0;i<length;++i){jobs[i]={startTime[i],endTime[i],profit[i]};}sort(jobs.begin(),jobs.end(),[](const vector<int> &job1,const vector<int> &job2)->bool{return job1[1]<job2[1];});vector<int> dp(length+1,0);for(int i=1;i<length+1;++i){int left=0,right=i-2;while(left<=right){int mid=(right-left)/2+left;if(jobs[mid][1]<=jobs[i-1][0]){left=mid+1;}else{right=mid-1;}}dp[i]=max(dp[i-1],dp[left]+jobs[i-1][2]);}return dp[length];}
};
4.执行结果
