企业官网建设流程全解析

LeetCode 630 课程表 III

一、题目原文

题号：630 标题：课程表 III（Course 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. 第1门：100天，第100天完成
2. 第3门：1000天，第1100天完成
3. 第2门：200天，第1300天完成
   第4门2000天，总时间会超过截止日期3200，无法安排。

示例2

输入：courses = [[1,2]] 输出：1

示例3

输入：courses = [[3,2],[4,3]] 输出：0

约束条件

• 1 <= courses.length <= 10^4
• 1 <= 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_time=0，大根堆heap=[]

1. 课程[100,200]
   total_time += 100 → total_time=100
   堆压入 -100。堆：[-100]
   total_time(100) ≤ 200，没问题。已选课程=1门

2. 课程[1000,1250]
   total_time +=1000 → total_time=1100
   堆压入 -1000。堆：[-1000,-100]
   1100 ≤1250，没问题。已选课程=2门

3. 课程[200,1300]
   total_time +=200 → total_time=1300
   堆压入 -200。堆：[-1000,-100,-200]
   1300 ≤1300，刚好满足。已选课程=3门

4. 课程[2000,3200]
   total_time += 2000 → total_time = 3300
   堆压入 -2000。堆：[-2000,-100,-200,-1000]
   现在 total_time=3300 > 3200，超标！
   弹出堆最大值（也就是-2000，原值2000）
   total_time -=2000 → total_time = 1300
   现在总时间1300 ≤3200，停止弹出。
   堆剩下：[-1000,-100,-200]，堆长度=3。

循环结束。堆的长度就是答案3 ✔

4. 为什么不能用别的贪心（排查漏洞，费曼查漏）

❌ 错误思路：优先选课时最短的课。
会翻车。短课截止日期非常早，你先选一堆短课，会占用时间，导致大量截止早的课直接错过。

❌ 暴力DFS枚举所有组合：n=1e4，直接爆炸，时间完全扛不住。

✅ 正确思路：按截止日期排序 + 大根堆动态替换最长课程
时间复杂度：排序 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】从小到大排序# key=lambda x:x[1]，取子数组第二个元素lastDay作为排序依据courses.sort(key=lambdax:x[1])# 大根堆，python heapq是小根堆，我们存储负数模拟大根堆max_heap=[]# total_time：当前已经选中的所有课程，累计花费的总天数total_time=0# 遍历排序后的每一门课程forduration,last_dayincourses:# 把当前课程耗时加入总时间total_time+=duration# 压入堆：存负的duration，这样小根堆弹出最小负数等价取出原始最大durationheapq.heappush(max_heap,-duration)# 判断：总耗时是否超过当前这门课的截止日期# 如果超过，说明当前这套课程组合无法全部按时完成whiletotal_time>last_day:# 弹出堆里面最大时长的课程（取出负数，变回原值）longest_course=-heapq.heappop(max_heap)# 总时间减去这个最长课程耗时，相当于把这门课从计划中删掉total_time-=longest_course# 堆里面保存的就是我们最终选中的课程时长，堆长度=课程数量returnlen(max_heap)# 测试示例代码if__name__=="__main__":sol=Solution()# 示例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天，每个模块有截止复习节点。每天只能专心复习一个模块，计算最多能完成多少模块。

补充：如果需求改成「最大化收益」而不是最大化任务数量，贪心策略就失效，需要动态规划。本题目标是任务数量最大化，贪心+堆才成立。

五、考点总结（面试）

1. 贪心策略选择：排序关键字（截止日期）
2. 堆的使用，Python用负数模拟大根堆
3. 贪心的交换论证：为什么删掉最长课程是局部最优、最终得到全局最优
4. 复杂度分析 O(n log n)