1235. 规划兼职工作

╰半夏微凉° 2024-04-01 10:40 38阅读 0赞

问题描述：

> 你打算利用空闲时间来做兼职工作赚些零花钱。  
> 这里有 n 份兼职工作，每份工作预计从 startTime\[i\] 开始到 endTime\[i\]结束，报酬为 profit\[i\]。
> 
> 给你一份兼职工作表，  
> 包含开始时间 startTime，结束时间 endTime 和预计报酬 profit三个数组，请你计算并返回可以获得的最大报酬。
> 
> 注意，时间上出现重叠的 2 份工作不能同时进行。  
> 如果你选择的工作在时间 X结束，那么你可以立刻进行在时间 X 开始的下一份工作。

![在这里插入图片描述][fe54e0ff336a405fb594c401ef990bc9.png]

问题思路：

### 方法一：动态规划 ###

按照endTime进去排序，然后维护dp数组，保存接到第几份任务时能获得的最大报酬。  
dp\[i\]: 当选到第i份工作时，可以拿到的最大报酬  
dp\[i\]=max\{dp\[j\]\}+profit， i>j,且startTime\[j\]>=endTime\[i\]  
用一个Job对象来存储startTime、endTime和profile

### 方法二：动态规划+二分 ###

动态规划是每次遍历到dp\[i\]，都需要查询前面所有的dp\[j\]，然后寻找最大的那个。  
可是原数组已经按右端点排序了，即按结束时间排序，那我们直接找到第一个小于dp\[i\]开始时间的区间，即dp\[j\].endTime < dp\[i\].startTime.  
然后插入它后面，比较薪酬取最大值插入即可。

class Solution {
        
    
    
        class Job implements Comparable<Job>{
        
    
            private int startTime;
            private int endTime;
            private int profit;
            public Job(int startTime, int endTime, int profit){
        
                this.startTime = startTime;
                this.endTime = endTime;
                this.profit = profit;
            }
    
             public int compareTo(Job job){
        
                return Integer.compare(this.endTime, job.endTime);
            }
    
        }
       public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        
            // 先按结束时间排序
            Job[] jobs = new Job[startTime.length];
            for (int i = 0; i < startTime.length; i++) {
        
                Job job = new Job(startTime[i],endTime[i],profit[i]);
                jobs[i] = job;
            }
            Arrays.sort(jobs);
             // dp存放最大报酬
            int[] dp= new int[startTime.length];
            dp[0] = jobs[0].profit;
            // 最大报酬
            int total = jobs[0].profit;
            
    
            for (int i = 1; i < jobs.length; i++) {
        
                // dp[i] = max{dp[j]}+profit[i], 其中i>j,startTime[i] >= endTime[j]
                // 直接找到当前的最晚结束时间，从它开始去对比薪酬
                // 返回前面i-1个元素中，不和i个区间时间重叠的起始区间
                int k = findMaxLat(jobs, i-1,jobs[i].startTime);
    
                // 如果该区间与前面的所有区间重叠
                if(k<0){
        
                    dp[i] = Math.max(dp[i-1],jobs[i].profit);
                }else{
        
                    dp[i] = Math.max(dp[i-1],dp[k]+jobs[i].profit);
                }
                total = Math.max(total, dp[i]);
            }
            return total;
    
        }
    
        // 找到最后一个小于K的数
        public int findMaxLat(Job[] jobs, int right, int k){
        
    
            int left = -1;
            int mid;
    
            while (left<right){
        
                mid = (left+right+1)/2;
                if(jobs[mid].endTime <= k){
        
                    left = mid;
                }else{
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }

[fe54e0ff336a405fb594c401ef990bc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/018b134249204a8587942712866cb427.png