Leetcode 1235. Maximum Profit in Job Scheduling (python)

题目

解法1：dp

这倒题目用dp来做是挺明显的，但是dp的元素代表什么很关键。如果dp元素代表时间的话，那这个题目就很难做了。正确的做法应该是用区间来代表dp的元素，这样就变成了对于每个元素取或者不取两种情况了。具体的解法如下：

• 将各个区间按照结尾进行排序
• dp[i]代表从前i个区间中选择，最多可以获取多大的利润
• 对于第i个区间，分取和不取两种情况
• 如果取第i个区间，那么需要向前找到j区间，这个区间的结束时间在i区间开始时间之前，这样总理论就等于从前j个区间中取获得的利润加上第i个区间的利润
  状态转移方程

dp[i] = max(dp[i-1],dp[j]+profit_i) where j is the first nonoverlapping interval to i 

class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:n = len(startTime)segments = []for i in range(n):segments.append([startTime[i],endTime[i],profit[i]])segments.sort(key=lambda x:x[1])dp = [0]*nfor i in range(n):# if we don't take iif i>0:dp[i] = dp[i-1]# if we take ifor j in range(i-1,-1,-1):if segments[j][1]<=segments[i][0]:dp[i] = max(dp[i],dp[j]+segments[i][2])break# take into count when interval i is the first onedp[i] = max(dp[i],segments[i][2])return dp[-1]

对于最后一行是必须要的，第一个原因是dp[0]需要初始化。另外更重要的原因举个例子，如果第一个区间是[2,3], profit是10，第二个区间是[1,4]，profit是100.这个时候dp[0]=10，但是如果没有最后一个比较，dp[1]会是10，而正确的应该是100

解法2：dp+binary search

利用左闭右开寻找第一个符合条件的区间j。关于二分的学习，看这里https://blog.csdn.net/qq_37821701/article/details/108772806

class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:n = len(startTime)segments = []for i in range(n):segments.append([startTime[i],endTime[i],profit[i]])segments.sort(key=lambda x:x[1])dp = [0]*nfor i in range(n):# if we don't take iif i>0:dp[i] = dp[i-1]# if we take il = 0r = iwhile l+1<r:mid = l+(r-l)//2if segments[mid][1]<=segments[i][0]:l = midelse:r = midif segments[l][1]<=segments[i][0]:dp[i] = max(dp[i],dp[l]+segments[i][2])dp[i] = max(dp[i],segments[i][2])return dp[-1]

上面两种解法，对于大数据规模来说肯定是解法2更快，但实际上这两道题leetcode的测试数据很小，所以解法一提交结果更快

二刷

一开始的时候还是写了O(n^2)的解法

class Solution {
    
public:static bool comparer(const vector<int>& a, const vector<int>& b){
    return a[0] < b[0];}int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    vector<vector<int>> jobs;int n = startTime.size();for(int i=0;i<n;i++){
    jobs.push_back({
    startTime[i],endTime[i],profit[i]});}sort(jobs.begin(),jobs.end(),comparer);vector<int> dp(n+1,0);// dp[0] = jobs[0][2];for(int i=1;i<n+1;i++){
    for(int j=i-1;j>=0;j--){
    if(j == 0 || jobs[j-1][1] <= jobs[i-1][0]){
    dp[i] = max(dp[i],dp[j]+jobs[i-1][2]);}}}return *max_element(dp.begin(),dp.end());}
};

tle了之后想到了用二分搜索，但是实际上上面的dp写法是不能够进行二分搜索的。因为上面dp[i]的定义是以i位置的区间作为最后一个job，而且必须是take这个job的。所以当dp过程中往前找的时候，必须要看完全部前面的case才可以，而不是碰到第一个满足条件的job就可以，这也是为什么做不了二分搜索。
其实做一点改变就可以了，把dp[i]的定义改成到第i个区间截止时间为止，所能得到的最大profit，而不是必须以i个区间为结尾。所以其实本质上是个背包问题。也只需要在代码里面加上dp[i] = dp[i-1]即可，同时按照结束时间来排序，这样因为当后面的区间结束的更晚，所以dp[i]必定是大于等于dp[i-1]的，同时注意边界条件的处理

不用二分搜索的版本：

class Solution {
    
public:static bool comparer(const vector<int>& a, const vector<int>& b){
    return a[1] < b[1];}int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    vector<vector<int>> jobs;int n = startTime.size();for(int i=0;i<n;i++){
    jobs.push_back({
    startTime[i],endTime[i],profit[i]});}sort(jobs.begin(),jobs.end(),comparer);vector<int> dp(n,0);for(int i=0;i<n;i++){
    if(i > 0){
    dp[i] = dp[i-1];}dp[i] = max(dp[i],jobs[i][2]);for(int j=i-1;j>=0;j--){
    if(jobs[j][1] <= jobs[i][0]){
    dp[i] = max(dp[i],dp[j]+jobs[i][2]);break;}}}return dp.back();}
};

加上二分搜索的版本：

class Solution {
    
public:static bool comparer(const vector<int>& a, const vector<int>& b){
    return a[1] < b[1];}int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    vector<vector<int>> jobs;int n = startTime.size();for(int i=0;i<n;i++){
    jobs.push_back({
    startTime[i],endTime[i],profit[i]});}sort(jobs.begin(),jobs.end(),comparer);vector<int> dp(n,0);for(int i=0;i<n;i++){
    if(i > 0){
    dp[i] = dp[i-1];}dp[i] = max(dp[i],jobs[i][2]);/*for(int j=i-1;j>=0;j--){if(jobs[j][1] <= jobs[i][0]){dp[i] = max(dp[i],dp[j]+jobs[i][2]);break;}}*/int l = 0;int r = i;while(l+1<r){
    int mid = l + (r-l)/2;if(jobs[mid][1] > jobs[i][0]){
    r = mid;}else{
    l = mid;}}if(jobs[l][1] <= jobs[i][0]){
    dp[i] = max(dp[i],dp[l]+jobs[i][2]);}}return dp.back();}
};