leetcode 630. 课程表 III-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 630. 课程表 III。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这里有 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

提示=
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)