广州网站模板建站,公司网站开发费用入什么科目,一个地址能注册几个公司,开题报告网站开发方法1.题目基本信息
1.1.题目描述
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作#xff0c;每份工作预计从 startTime[i] 开始到 endTime[i] 结束#xff0c;报酬为 profit[i]。
给你一份兼职工作表#xff0c;包含开始时间 startTime#xff0c;结束时…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则kj1。这里使用左闭右闭的未标记区间的方式进行二分
3.解题代码
Python代码
class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) - int:lengthlen(startTime)jobssorted(zip(startTime,endTime,profit),keylambda item:item[1])# 第一步状态定义dp[i]为前i个兼职工作的最大报酬dp[0]*(length1)# 第二步状态转移dp[i]max(dp[i-1],dp[k]profit[i-1]) profit[i-1]为第i个工作的报酬假设从0到i-2工作中最后一个endTime小于等于i-1工作的startTime的工作下标为j则kj1。这里使用左闭右闭的未标记区间的方式进行二分for i in range(1,length1):left,right0,i-2 # 左闭右闭while leftright:mid(right-left)//2leftif jobs[mid][1]jobs[i-1][0]:leftmid1else:rightmid-1kleft # right1dp[i]max(dp[i-1],dp[k]jobs[i-1][2])return dp[-1]C代码
class Solution {
public:int jobScheduling(vectorint startTime, vectorint endTime, vectorint profit) {int lengthstartTime.size();vectorvectorint jobs(length);for(int i0;ilength;i){jobs[i]{startTime[i],endTime[i],profit[i]};}sort(jobs.begin(),jobs.end(),[](const vectorint job1,const vectorint job2)-bool{return job1[1]job2[1];});vectorint dp(length1,0);for(int i1;ilength1;i){int left0,righti-2;while(leftright){int mid(right-left)/2left;if(jobs[mid][1]jobs[i-1][0]){leftmid1;}else{rightmid-1;}}dp[i]max(dp[i-1],dp[left]jobs[i-1][2]);}return dp[length];}
};4.执行结果
