这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
示例 1：
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
示例 2：
输入：courses = [[1,2]]
输出：1
示例 3：
输入：courses = [[3,2],[4,3]]
输出：0文章来源：https://www.toymoban.com/news/detail-588436.html
提示=
1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104
leetcode 630
思路：
可以用贪心法的思路来做，
1.假如有两门课 (t1, d1) 和 (t2, d2)，假如 d1 <= d2，我们应该先学前者，再学后者，这样总的课程数是最优的
2.根据1，我们可以把课程根据 lastDay 从小到大排序，当遍历到 (ti，di) 课程时，如果学 ti 课程，总时间超过了 di, 我们需要从已经打算学的课程列表里面挑选出 duration 最大的课程和 ti 比较，如果 duration > ti, 则 duration 课程出列，ti 入列(减少 总 duration 的上限)，最后课程列表(可用最大值堆来实现)的长度即为最长的课程数。文章来源地址https://www.toymoban.com/news/detail-588436.html
from functools import cmp_to_key
import heapq
class Solution:
def compare(self, a, b):
if a[1] <= b[1]:
return -1
else:
return 1
def scheduleCourse(self, courses: List[List[int]]) -> int:
a = []
for x in courses: ### 过滤掉 duration > lastDay 的课程
if x[0] <= x[1]:
a.append(x)
if len(a) <= 1:
return len(a)
nums = sorted(a, key=cmp_to_key(self.compare)) ## 按 lastDay 从小到大排序
ss = []
heapq.heappush(ss, -nums[0][0]) ### 默认是最小值堆, 加负号变成最大值堆
curSum = nums[0][0]
for i in range(1, len(nums)):
if curSum + nums[i][0] <= nums[i][1]:
heapq.heappush(ss, -nums[i][0])
curSum += nums[i][0]
else: ### 存 duration 小的, 比如输入是[[5,5],[4,6],[2,6]] 这种
if nums[i][0] < -ss[0]:
curSum += nums[i][0] + ss[0]
heapq.heappop(ss)
heapq.heappush(ss, -nums[i][0])
return len(ss)
到了这里，关于leetcode 630. 课程表 III的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
