Leetcode 1235. 规划兼职工作

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.执行结果