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+left
                if jobs[mid][1]<=jobs[i-1][0]:
                    left=mid+1
                else:
                    right=mid-1
            k=left  # right+1
            dp[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.执行结果