初学python记录:力扣1235. 规划兼职工作

server/2024/11/17 2:39:11/

题目:

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]

给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。

注意,时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。

提示:

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
  • 1 <= startTime[i] < endTime[i] <= 10^9
  • 1 <= profit[i] <= 10^4

思考:

解法一——动态规划(以时间作为划分)

设f(x)为在时间为x时能获得的最大报酬,

设正好在x结束的工作开始于时间m,报酬为p,那么

f(x) = max(f(x-1), f(m_1)+p_1, f(m_2)+p_2, ......) 

代码如下:

python">class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:# 动态规划:dp[i]表示在时间为i时能获得的最大报酬# f(x) = max(f(x-1), f(m)+p)   设正好在x结束的所有工作开始于m,报酬为pn = max(endTime)dp = [0 for _ in range(n+1)]for i in range(2, n+1):candidate = []  # 记录所有"f(m)+p"for index, value in enumerate(endTime):if value == i:candidate.append(dp[startTime[index]] + profit[index])if candidate:dp[i] = max(dp[i - 1], max(candidate))else:dp[i] = dp[i - 1]return dp[n]

超时,卡在第 21 / 35 个例子:

 

优化 

可以将遍历endtime数组找到刚好在x结束的所有工作这一步提到最前面,避免每次计算f(x)时都要遍历一次。代码如下:

python">from collections import defaultdict
class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:# 动态规划:dp[i]表示在时间为i时能获得的最大报酬# f(x) = max(f(x-1), f(m)+p)   设正好在x结束的所有工作开始于m,报酬为pn = max(endTime)dp = [0 for _ in range(n+1)]end_index = defaultdict(list)   # 键为结束时间,值为这份工作的索引for index, time in enumerate(endTime):end_index[time].append(index)for i in range(2, n+1):if not end_index[i]:dp[i] = dp[i - 1]else:candidate = []  # 记录所有"f(m)+p"for index in end_index[i]:candidate.append(dp[startTime[index]] + profit[index])dp[i] = max(dp[i - 1], max(candidate))return dp[n]

时间上确实加快了,但是卡在一个特殊的测试例子上,超内存了:

原因是只有四项工作待选,但是用时间划分的话,dp数组的长度有1000000001,显然在这种情况下仍然按时间划分造成了内存极大浪费。

解法二——动态规划(以工作作为划分)

那么换一个思路,将所有工作按结束时间排序,以是否选择每一项工作作为划分。

设f(x)表示在第x个结束的工作结束时,能获得的最大报酬,即 选择工作x 或者 不选择工作x 这两种决策得到的报酬更大值。公式如下,其中y是满足endtime(y) <= starttime(x) 条件的工作索引最大值,如果不存在这样的y,则f(y)取0:

 f(x) = max(f(x-1), f(y)+profit(x))

为了减少耗时,这里找y使用二分查找。代码如下:

python">from collections import defaultdict
class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:# 动态规划:f(x)表示在第x个结束的工作结束时,能获得的最大报酬,即 选择工作x 或者 不选择工作x 的报酬更大值# 公式如下,其中y是满足endtime(y) <= starttime(x) 条件的工作索引最大值,如果不存在这样的y,则f(y)取0# f(x) = max(f(x-1), f(y)+profit(x))# 将所有工作按结束时间排序combined_list = list(zip(startTime, endTime, profit))combined_list = sorted(combined_list, key = lambda x : x[1])n = len(profit)dp = [-1 for _ in range(n)]dp[0] = combined_list[0][2]for x in range(1, n):# 找到工作y:满足endtime(y) <= starttime(x) 条件的最大值left = 0right = x - 1f_y = 0while left <= right:mid = (left + right) // 2if combined_list[mid][1] <= combined_list[x][0]:f_y = dp[mid]left = mid + 1else:right = mid - 1# f(x) = max(f(x-1), f(y)+profit(x))dp[x] = max(dp[x-1], f_y + combined_list[x][2])return dp[n-1]

提交通过,耶耶耶: 

 


http://www.ppmy.cn/server/32467.html

相关文章

c#使用Elastic.Clients.Elasticsearch 库进行ElasticSearch的增删改查操作,根据变量动态构建查询条件。

实体类Shop结构: public class Shop {public string UUID { set; get; }public string ItemType { set; get; }public long ItemId { set; get; }public string ItemName { set; get; }public long Gold { set; get; }public long Number { set; get; }public string Data { s…

14_Scala面向对象编程_属性

属性 1.类中属性声明 // 1.给Scala声明属性&#xff1b;var name :String "zhangsan"val age :Int 302.系统默认赋值 scala由于初始化变量必须赋值&#xff0c;为了解决此问题可以采用下划线赋值&#xff0c;表示系统默认赋值 , –但是此方法局限于变量&…

js方法返回类型

在JavaScript中&#xff0c;方法可以是以下几种形式&#xff1a; 1. **函数声明**&#xff1a;传统的函数声明方式。 javascript function greet() { console.log(Hello, World!); } 2. **函数表达式**&#xff1a;使用变量赋值的方式定义函数。 javascript const greet…

基于Springboot的旅游管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的旅游管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…

从零开始学AI绘画,万字Stable Diffusion终极教程(一)

【第1期】SD入门 2022年8月&#xff0c;一款叫Stable Diffusion的AI绘画软件开源发布&#xff0c;从此开启了AIGC在图像上的爆火发展时期 率先学会SD的人&#xff0c;已经挖掘出了越来越多AI绘画有趣的玩法 从开始的AI美女、线稿上色、真人漫改、头像壁纸 到后来的AI创意字、AI…

在Django中实现多用户角色和权限管理的方法

在Django中实现多用户角色和权限管理可以通过以下步骤实现&#xff1a; 定义用户角色模型&#xff1a;首先&#xff0c;定义一个用户角色模型&#xff0c;该模型表示不同的用户角色&#xff0c;例如管理员、普通用户、编辑等。 from django.db import modelsclass Role(model…

Cocos Creator 3D物理引擎的物理参数控制详解

前言 Cocos Creator是一款基于JavaScript和TypeScript的开源游戏引擎&#xff0c;它提供了强大的3D物理引擎&#xff0c;可以帮助开发者实现各种物理效果。在Cocos Creator中&#xff0c;我们可以通过控制物理参数来实现不同的物理效果&#xff0c;比如重力、碰撞检测、摩擦力…

网络安全是智能汽车下一个要卷的方向?

2024年一季度&#xff0c;中国汽车市场延续了2023年的风格&#xff0c;核心就是「卷」。 2023年&#xff0c;我国汽车市场爆发「最强价格战」&#xff0c;燃油车的市场空间不断被挤压&#xff0c;如今只剩下最后一口气。近日乘联会发布4月1-14日最新数据&#xff0c;新能源&am…