力扣 每日一题 1235. 规划兼职工作【难度：困难，rating: 2022】（动态规划+二分查找）

题目链接

https://leetcode.cn/problems/maximum-profit-in-job-scheduling/

题目来源于：第159场周赛 Q4 rating: 2022

思路

将所有工作按结束时间排序，然后考虑动态规划：

1. 直接放弃第 i 个工作，那么保持前 i-1 个工作的收益，$dp[i]=dp[i-1]。$
2. 设法选上第 i 个工作，那么$dp[i]=dp[k]+profit[i]$，其中 k 必须满足 $end[k]<=start[i]$，并且 k 要尽可能大，这样才能让 dp[k] 尽可能大。

遍历一次需要 $O(n)$，每次二分查找 k 需要 $O(logn)$，所以整体复杂度$O(nlogn)$。

代码

// dp[i]=max(dp[i-1],dp[k]+profit[i])
// dp[i-1]就是直接放弃第i个工作，保持前i-1个工作的收益
// k是在第i个工作开始前能够结束的工作编号的最大值（即end[k]<=start[i]，k尽可能大）
// dp[k]+profit[i]就是设法加上第i个工作的收益，那么k必须在满足end[k]<=start[i]的前提下尽可能大，dp[k]才能尽可能大
class Solution {
    static const int N=5e4+10;
    int dp[N];
    struct node{
        int st,ed,val;
    }a[N];

public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n=startTime.size();
        for(int i=1;i<=n;i++){
            a[i].st=startTime[i-1];
            a[i].ed=endTime[i-1];
            a[i].val=profit[i-1];
        }
        sort(a+1,a+n+1,[](node s1,node s2){return s1.ed<s2.ed;}); // 第三个参数cmp传入匿名函数
        sort(endTime.begin(),endTime.end()); // 注意endTime[i]的下标比a[i].ed的下标少1

        dp[0]=0;
        for(int i=1;i<=n;i++){
            // 满足end[k]<=start[i]的k的最大值，k的范围为[1,i-1]
            // upper_bound找的是 > 的，再 -1 就是 <=，下标还得 +1，所以 -1+1 抵消掉了
            int k=upper_bound(endTime.begin(),endTime.begin()+i-1,a[i].st)-endTime.begin();
            dp[i]=max(dp[i-1],dp[k]+a[i].val);
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32