LeetCode 630 课程表 III一、题目原文题号630 标题课程表 IIICourse Schedule III 难度Hard题目描述这里有n门不同的在线课程按从1到n编号。给你一个数组courses其中courses[i] [duration_i, lastDay_i]表示第i门课将会持续上duration_i天课并且必须在不晚于lastDay_i的时候完成。你的学期从第1天开始。且不能同时修读两门及两门以上的课程。返回你最多可以修读的课程数目。示例示例1输入courses [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出3解释最多修3门课第1门100天第100天完成第3门1000天第1100天完成第2门200天第1300天完成第4门2000天总时间会超过截止日期3200无法安排。示例2输入courses [[1,2]] 输出1示例3输入courses [[3,2],[4,3]] 输出0约束条件1 courses.length 10^41 duration_i, lastDay_i 10^4二、费曼学习法讲解破解过程假装给小白讲明白费曼4步确定目标 → 模拟教学大白话→ 找出卡壳漏洞 → 简化重讲1. 问题大白话翻译你有一堆网课。每门课要连续学t天必须在第d天之前上完。一次只能学一门一门接一门学。问最多能上完几门课目标课程数量最大化不是总学习时间最大化。重点我们想要门数最多不是学的总时长最长。同样数量的课我们希望总耗时尽量小留出时间给后面更多课程。2. 贪心策略怎么想到的核心思想 策略1优先安排截止时间更早的课理由截止早的课不先安排后面一定会错过截止日期截止晚的课可以往后放。第一步所有课程按照 lastDay截止日期从小到大排序。 策略2如果加入新课之后总时间超过当前课的截止日期删掉已经选的里面最耗时的那一门为什么这么干举个例子你已经选了几门课总耗时S。现在新增一门课S新课时长 当前课截止日期。现在我们手里的课程集合数量是k门。如果把集合里最费时间的课踢掉换成这门新课课程总数不变还是k门总耗时变少总耗时变小后面更容易塞进去更多新课。这就是本题最巧妙的贪心牺牲最长的旧课保留课程数量不变压缩总时间。 用什么工具快速拿到当前已选课程里最长时长大根堆最大堆Python自带heapq库默认是小根堆。实现大根堆的技巧存负数。3. 完整流程模拟用示例1原始输入[[100,200],[200,1300],[1000,1250],[2000,3200]]① 按截止日期排序[[100,200], [1000,1250], [200,1300], [2000,3200]]② 初始化总时间total_time0大根堆heap[]课程[100,200]total_time 100 → total_time100堆压入 -100。堆[-100]total_time(100) ≤ 200没问题。已选课程1门课程[1000,1250]total_time 1000 → total_time1100堆压入 -1000。堆[-1000,-100]1100 ≤1250没问题。已选课程2门课程[200,1300]total_time 200 → total_time1300堆压入 -200。堆[-1000,-100,-200]1300 ≤1300刚好满足。已选课程3门课程[2000,3200]total_time 2000 → total_time 3300堆压入 -2000。堆[-2000,-100,-200,-1000]现在 total_time3300 3200超标弹出堆最大值也就是-2000原值2000total_time -2000 → total_time 1300现在总时间1300 ≤3200停止弹出。堆剩下[-1000,-100,-200]堆长度3。循环结束。堆的长度就是答案3 ✔4. 为什么不能用别的贪心排查漏洞费曼查漏❌ 错误思路优先选课时最短的课。会翻车。短课截止日期非常早你先选一堆短课会占用时间导致大量截止早的课直接错过。❌ 暴力DFS枚举所有组合n1e4直接爆炸时间完全扛不住。✅ 正确思路按截止日期排序 大根堆动态替换最长课程时间复杂度排序 O(n log n)堆操作每门课最多进出堆一次 O(n log n)总复杂度 O(n log n)可以处理1e4的数据。空间复杂度O(n)最坏全部课程入堆。5. 一句话总结算法先把课程按截止时间从小到大排逐个加入累加总耗时用大根堆保存所选课程时长一旦总耗时超过当前课截止日期就把已经选的里面耗时最长的课删掉维持课程数量尽可能多、总耗时尽可能小最后堆里面元素数量就是最多课程数。三、Python完整代码每行详细注释# 导入堆工具python内置heapq只实现小根堆importheapq# 类型注解需要导入ListfromtypingimportListclassSolution:defscheduleCourse(self,courses:List[List[int]])-int: Leetcode 630 课程表 III :param courses: 二维列表courses[i] [课程持续时间duration,最晚完成日期lastDay] :return: int最多可以修读课程数量 # 第一步把课程按照【最晚完成日期lastDay】从小到大排序# keylambda x:x[1]取子数组第二个元素lastDay作为排序依据courses.sort(keylambdax:x[1])# 大根堆python heapq是小根堆我们存储负数模拟大根堆max_heap[]# total_time当前已经选中的所有课程累计花费的总天数total_time0# 遍历排序后的每一门课程forduration,last_dayincourses:# 把当前课程耗时加入总时间total_timeduration# 压入堆存负的duration这样小根堆弹出最小负数等价取出原始最大durationheapq.heappush(max_heap,-duration)# 判断总耗时是否超过当前这门课的截止日期# 如果超过说明当前这套课程组合无法全部按时完成whiletotal_timelast_day:# 弹出堆里面最大时长的课程取出负数变回原值longest_course-heapq.heappop(max_heap)# 总时间减去这个最长课程耗时相当于把这门课从计划中删掉total_time-longest_course# 堆里面保存的就是我们最终选中的课程时长堆长度课程数量returnlen(max_heap)# 测试示例代码if__name____main__:solSolution()# 示例1test1[[100,200],[200,1300],[1000,1250],[2000,3200]]print(sol.scheduleCourse(test1))# 预期输出3# 示例2test2[[1,2]]print(sol.scheduleCourse(test2))# 预期输出1# 示例3test3[[3,2],[4,3]]print(sol.scheduleCourse(test3))# 预期输出0代码运行结果3 1 0四、应用场景举例这个模型是单机器、带截止时间、最大化任务数量调度算法工程上很常用。场景1在线学习平台课程推荐排期平台用户有一堆课程每门课需要连续学习固定时长并且有截止时间证书到期同一时间只能学习一门。算法算出用户最多能完成多少课程自动给用户规划最优学习计划。场景2任务调度服务器离线批任务服务器串行执行任务每个任务有执行耗时和最晚完成截止时间。目标是尽可能多完成任务不是尽可能多跑计算量。比如定时报表、数据清洗任务一次只能跑一个任务。场景3项目外包接单你一个人接项目每个项目需要连续干t天必须在d天前交付同一时间只能做一个项目。想接最多数量项目而不是赚最多钱用这个算法筛选可以接的项目集合。场景4考研/备考规划你有很多复习模块每个模块要连续复习t天每个模块有截止复习节点。每天只能专心复习一个模块计算最多能完成多少模块。补充如果需求改成「最大化收益」而不是最大化任务数量贪心策略就失效需要动态规划。本题目标是任务数量最大化贪心堆才成立。五、考点总结面试贪心策略选择排序关键字截止日期堆的使用Python用负数模拟大根堆贪心的交换论证为什么删掉最长课程是局部最优、最终得到全局最优复杂度分析 O(n log n)
LeetCode 630 课程表 III一、题目原文题号630 标题课程表 IIICourse Schedule III 难度Hard题目描述这里有n门不同的在线课程按从1到n编号。给你一个数组courses其中courses[i] [duration_i, lastDay_i]表示第i门课将会持续上duration_i天课并且必须在不晚于lastDay_i的时候完成。你的学期从第1天开始。且不能同时修读两门及两门以上的课程。返回你最多可以修读的课程数目。示例示例1输入courses [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出3解释最多修3门课第1门100天第100天完成第3门1000天第1100天完成第2门200天第1300天完成第4门2000天总时间会超过截止日期3200无法安排。示例2输入courses [[1,2]] 输出1示例3输入courses [[3,2],[4,3]] 输出0约束条件1 courses.length 10^41 duration_i, lastDay_i 10^4二、费曼学习法讲解破解过程假装给小白讲明白费曼4步确定目标 → 模拟教学大白话→ 找出卡壳漏洞 → 简化重讲1. 问题大白话翻译你有一堆网课。每门课要连续学t天必须在第d天之前上完。一次只能学一门一门接一门学。问最多能上完几门课目标课程数量最大化不是总学习时间最大化。重点我们想要门数最多不是学的总时长最长。同样数量的课我们希望总耗时尽量小留出时间给后面更多课程。2. 贪心策略怎么想到的核心思想 策略1优先安排截止时间更早的课理由截止早的课不先安排后面一定会错过截止日期截止晚的课可以往后放。第一步所有课程按照 lastDay截止日期从小到大排序。 策略2如果加入新课之后总时间超过当前课的截止日期删掉已经选的里面最耗时的那一门为什么这么干举个例子你已经选了几门课总耗时S。现在新增一门课S新课时长 当前课截止日期。现在我们手里的课程集合数量是k门。如果把集合里最费时间的课踢掉换成这门新课课程总数不变还是k门总耗时变少总耗时变小后面更容易塞进去更多新课。这就是本题最巧妙的贪心牺牲最长的旧课保留课程数量不变压缩总时间。 用什么工具快速拿到当前已选课程里最长时长大根堆最大堆Python自带heapq库默认是小根堆。实现大根堆的技巧存负数。3. 完整流程模拟用示例1原始输入[[100,200],[200,1300],[1000,1250],[2000,3200]]① 按截止日期排序[[100,200], [1000,1250], [200,1300], [2000,3200]]② 初始化总时间total_time0大根堆heap[]课程[100,200]total_time 100 → total_time100堆压入 -100。堆[-100]total_time(100) ≤ 200没问题。已选课程1门课程[1000,1250]total_time 1000 → total_time1100堆压入 -1000。堆[-1000,-100]1100 ≤1250没问题。已选课程2门课程[200,1300]total_time 200 → total_time1300堆压入 -200。堆[-1000,-100,-200]1300 ≤1300刚好满足。已选课程3门课程[2000,3200]total_time 2000 → total_time 3300堆压入 -2000。堆[-2000,-100,-200,-1000]现在 total_time3300 3200超标弹出堆最大值也就是-2000原值2000total_time -2000 → total_time 1300现在总时间1300 ≤3200停止弹出。堆剩下[-1000,-100,-200]堆长度3。循环结束。堆的长度就是答案3 ✔4. 为什么不能用别的贪心排查漏洞费曼查漏❌ 错误思路优先选课时最短的课。会翻车。短课截止日期非常早你先选一堆短课会占用时间导致大量截止早的课直接错过。❌ 暴力DFS枚举所有组合n1e4直接爆炸时间完全扛不住。✅ 正确思路按截止日期排序 大根堆动态替换最长课程时间复杂度排序 O(n log n)堆操作每门课最多进出堆一次 O(n log n)总复杂度 O(n log n)可以处理1e4的数据。空间复杂度O(n)最坏全部课程入堆。5. 一句话总结算法先把课程按截止时间从小到大排逐个加入累加总耗时用大根堆保存所选课程时长一旦总耗时超过当前课截止日期就把已经选的里面耗时最长的课删掉维持课程数量尽可能多、总耗时尽可能小最后堆里面元素数量就是最多课程数。三、Python完整代码每行详细注释# 导入堆工具python内置heapq只实现小根堆importheapq# 类型注解需要导入ListfromtypingimportListclassSolution:defscheduleCourse(self,courses:List[List[int]])-int: Leetcode 630 课程表 III :param courses: 二维列表courses[i] [课程持续时间duration,最晚完成日期lastDay] :return: int最多可以修读课程数量 # 第一步把课程按照【最晚完成日期lastDay】从小到大排序# keylambda x:x[1]取子数组第二个元素lastDay作为排序依据courses.sort(keylambdax:x[1])# 大根堆python heapq是小根堆我们存储负数模拟大根堆max_heap[]# total_time当前已经选中的所有课程累计花费的总天数total_time0# 遍历排序后的每一门课程forduration,last_dayincourses:# 把当前课程耗时加入总时间total_timeduration# 压入堆存负的duration这样小根堆弹出最小负数等价取出原始最大durationheapq.heappush(max_heap,-duration)# 判断总耗时是否超过当前这门课的截止日期# 如果超过说明当前这套课程组合无法全部按时完成whiletotal_timelast_day:# 弹出堆里面最大时长的课程取出负数变回原值longest_course-heapq.heappop(max_heap)# 总时间减去这个最长课程耗时相当于把这门课从计划中删掉total_time-longest_course# 堆里面保存的就是我们最终选中的课程时长堆长度课程数量returnlen(max_heap)# 测试示例代码if__name____main__:solSolution()# 示例1test1[[100,200],[200,1300],[1000,1250],[2000,3200]]print(sol.scheduleCourse(test1))# 预期输出3# 示例2test2[[1,2]]print(sol.scheduleCourse(test2))# 预期输出1# 示例3test3[[3,2],[4,3]]print(sol.scheduleCourse(test3))# 预期输出0代码运行结果3 1 0四、应用场景举例这个模型是单机器、带截止时间、最大化任务数量调度算法工程上很常用。场景1在线学习平台课程推荐排期平台用户有一堆课程每门课需要连续学习固定时长并且有截止时间证书到期同一时间只能学习一门。算法算出用户最多能完成多少课程自动给用户规划最优学习计划。场景2任务调度服务器离线批任务服务器串行执行任务每个任务有执行耗时和最晚完成截止时间。目标是尽可能多完成任务不是尽可能多跑计算量。比如定时报表、数据清洗任务一次只能跑一个任务。场景3项目外包接单你一个人接项目每个项目需要连续干t天必须在d天前交付同一时间只能做一个项目。想接最多数量项目而不是赚最多钱用这个算法筛选可以接的项目集合。场景4考研/备考规划你有很多复习模块每个模块要连续复习t天每个模块有截止复习节点。每天只能专心复习一个模块计算最多能完成多少模块。补充如果需求改成「最大化收益」而不是最大化任务数量贪心策略就失效需要动态规划。本题目标是任务数量最大化贪心堆才成立。五、考点总结面试贪心策略选择排序关键字截止日期堆的使用Python用负数模拟大根堆贪心的交换论证为什么删掉最长课程是局部最优、最终得到全局最优复杂度分析 O(n log n)
