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

题目:

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

这里有 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, ......) 

代码如下:

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,报酬为p
        n = 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)时都要遍历一次。代码如下:

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,报酬为p
        n = 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使用二分查找。代码如下:

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 = 0
            right = x - 1
            f_y = 0
            while left <= right:
                mid = (left + right) // 2
                if combined_list[mid][1] <= combined_list[x][0]:
                    f_y = dp[mid]
                    left = mid + 1
                else:
                    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]

提交通过,耶耶耶: 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/591850.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[嵌入式AI从0开始到入土]17_Ascend C算子开发

[嵌入式AI从0开始到入土]嵌入式AI系列教程 注&#xff1a;等我摸完鱼再把链接补上 可以关注我的B站号工具人呵呵的个人空间&#xff0c;后期会考虑出视频教程&#xff0c;务必催更&#xff0c;以防我变身鸽王。 第1期 昇腾Altas 200 DK上手 第2期 下载昇腾案例并运行 第3期 官…

JDK14特性

JDK14 1 概述2 语法层面的变化1_instanceof的模式匹配(预览)2_switch表达式(标准)3_文本块改进(第二次预览)4_Records 记录类型(预览 JEP359) 3 API层面的变化4 关于GC1_G1的NUMA内存分配优化2_弃用SerialCMS,ParNewSerial Old3_删除CMS4_ZGC on macOS and Windows 4 其他变化1…

PPT基础

5种ppt仅可读形式 Ⅰ 开始选项卡 1.【幻灯片】组中&#xff1a;新建幻灯片&#xff0c;从大纲中导入幻灯片&#xff1b;修改幻灯片的版式&#xff1b;节&#xff08;新增节&#xff0c;重命名节&#xff09;。 2.【字体】组中&#xff1a;设置字体&#xff0c;字体大小&…

ctfshow web入门 sql注入 web224--web233

web224 扫描后台&#xff0c;发现robots.txt&#xff0c;访问发现/pwdreset.php &#xff0c;再访问可以重置密码 &#xff0c;登录之后发现上传文件 检查发现没有限制诶 上传txt,png,zip发现文件错误了 后面知道群里有个文件能上传 <? _$GET[1]_?>就是0x3c3f3d60245…

海外仓系统与跨境电商平台集成:有什么意义,为什么重要

跨境电商的发展趋势并没有丝毫放缓的迹象&#xff0c;这使得对高效率、综合性的海外仓的需求变得比以往任何时间都要多。 预测表明&#xff0c;未来一年跨境电商的市场份额将继续扩大。这一切都要求海外仓企业尽快提升仓储管理效率&#xff0c;在这个过程中&#xff0c;海外仓系…

小苹果

题目描述 小的桌子上放着几个苹果从左到右排成一列&#xff0c;编号为从1 到 。小苞是小的好朋友&#xff0c;每天她都会从中拿走一些苹果。每天在拿的时候&#xff0c;小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列…

扩展学习|本体研究进展

文献来源&#xff1a; 王向前,张宝隆,李慧宗.本体研究综述[J].情报杂志,2016,35(06):163-170. 一、本体的定义 本体概念被引入人工智能、知识工程等领域后被赋予了新的含义。然而不同的专家学者对本体的理解不同,所给出的定义也有所差异。 人工智能领域的学者Neches(1991)等人对…

StampedLock(戳记锁)源码解读与使用

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java源码解读-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 1. 前言 我们在上一篇写ReentrantReadWriteLock读写锁的末尾留了一个小坑&#…

这书不错,古琴乐理实用教程(尹溧新编),有课学得通透。

通篇阅读后&#xff0c;发现这本书以古琴初习者、未系统接触过现代乐理的读者为对象&#xff0c;将复杂的古琴音乐理论简单化、通俗化。书中采用参照比较的方法、通俗易懂的语言、言简意赅的文字&#xff0c;并结合具体音乐作品将古琴研习中最主要的、最核心的理论知识进行简明…

进程间通信(3)信号量初识

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…

72.网络游戏逆向分析与漏洞攻防-角色与怪物信息的更新-完善利用角色与怪物创建的功能

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 如果看不懂、不知道现在做的什么&#xff0c;那就跟着做完看效果 现在的代码都是依据数据包来写的&#xff0c;如果看不懂代码&#xff0c;就说明没看懂数据包…

开源模型应用落地-LangChain高阶-Tools工具-集成agents(四)

一、前言 LangChain 的 tools 是一系列关键组件&#xff0c;它们提供了与外部世界进行交互的能力。通过适当的使用这些组件&#xff0c;可以简单实现如执行网络搜索以获取最新信息、调用特定的 API 来获取数据或执行特定的操作、与数据库进行交互以获取存储的信息等需求。 本章…

MATLAB - 自定义惯性矩阵

系列文章目录 前言 一、关键惯性约定 Simscape 多体软件在惯性定义中采用了一系列约定。请注意这些约定&#xff0c;因为如果手动进行惯性计算&#xff0c;这些约定可能会影响计算结果。如果您的惯性数据来自 CAD 应用程序或其他第三方软件&#xff0c;这些约定还可能影响到您需…

TranslatePress Pro插件下载:一键国际化,让您的网站走向世界

在全球化的今天&#xff0c;一个多语言的网站是连接不同文化和市场的桥梁。TranslatePress Pro插件&#xff0c;作为一款专为WordPress用户设计的多语言解决方案&#xff0c;以其简便的操作和强大的功能&#xff0c;帮助您的网站跨越语言障碍&#xff0c;吸引全球用户。 [Tran…

vector 的模拟实现

目录 1. vector 的核心框架 2. size 和 capacity 以及 empty 3. reserve 和 push_back 4. insert 5. erase 6. copy constructor 6.1. 第一个版本 6.2. 第二个版本 6.3. 第三个版本 7. operator 7.1. 第一个版本 7.2. 第二个版本 7.3. 第三个版本 8. constructor…

用自然语言即可完全控制用户界面;无需调整的文本至图片生成的ID定制方法;OpenAI构建应用指南

✨ 1: PyWinAssistant 用自然语言即可完全控制用户界面 PyWinAssistant是一个突破性的项目&#xff0c;它基于2023年12月31日发布的技术&#xff0c;代表了首个大型行为模型、开源Windows 10/11人工智能框架。这个框架的主要亮点在于它能够通过利用思维可视化&#xff08;Vis…

Java复习第十九天学习笔记(Cookie、Session登录),附有道云笔记链接

【有道云笔记】十九 4.7 Cookie、Session登录 https://note.youdao.com/s/VwpxfEim 一、会话技术简介 生活中会话 我&#xff1a; 小张&#xff0c;你会跳小苹果码&#xff1f; 小张&#xff1a; 会&#xff0c;怎么了&#xff1f; 我&#xff1a; 公司年会上要表演节目&a…

HTML_CSS学习:常用文本属性

一、文本颜色 相关代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>文本颜色</title><style>div{font-size: 90px;}.atguigu1{color: #238c20;}.atguigu2{color: rgb(2…

AI文章框架分析

大家在文章写作的时候结构难免会有点凌乱&#xff0c;但是自己可能无法发现问题所在&#xff0c;那么有没有一款工具可以帮你自动分析你写的文章框架存在的问题&#xff0c;然后并给你详细的分析报告呢&#xff1f;今天给大家介绍一下文件框架分析助手&#xff01; 使用说明 打…

jQuery Moblie 笔记14 开发跨平台移动设备网页

相关内容&#xff1a;jQuery Moblie基础、操作、移动设备仿真器、jQuery Moblie网页实例、jQuery Moblie的UI组件、…… jQuery推出了一套新的函数库jQuery Mobile&#xff0c;目的是希望能够统一当前移动设备的用户界面(UI)。 移动设备开发应用程序目前大致分为两种&#xff…