课程表 III

标签: 贪心 数组 排序 堆（优先队列）

难度: Hard

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

Submission

运行时间: 80 ms

内存: 20.9 MB

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        '''
        这题关键在于想明白总的 duration 和 last_day 是判断一个课程能不能上的关键，
        够一定能上，不够一定上不了，所以可以用用贪心减少总 duration，最大化课程数量。
        同时每考虑一个新的课程就尝试把它加到选课表中，短的优先，每一步的选择都是最优的，
        结果也自然是最优的。

        反向思维：不妨想象任意一个合法的选课表，其总时长一定是大于等于这个贪心算法的同课程数量的结果。不同于贪心算法选出来的课程一定可以用更优的课程替换掉。
        '''
        courses.sort(key=lambda c: c[1])  # 按照 last_day 从小到大排序

        h = []
        day = 0  # 已消耗时间
        for duration, last_day in courses:
            if day + duration <= last_day:  # 没有超过 last_day，直接学习
                day += duration
                heappush(h, -duration)  # 加负号变成最大堆
            elif h and duration < -h[0]:  # 该课程的时间比之前的最长时间要短
                # 反悔，撤销之前 duration 最长的课程，改为学习该课程
                # 节省出来的时间，能在后面上完更多的课程
                day += heapreplace(h, -duration) + duration
        return len(h)

Explain

这个题目可以用贪心算法来解决。首先将课程按照结束时间从小到大排序。然后遍历每门课程，如果当前已消耗的时间加上该课程的持续时间没有超过该课程的结束时间，就学习该课程。否则，如果该课程的持续时间比之前选择的课程中持续时间最长的还要短，就替换掉那门最长的课程，学习当前这门课程。这样可以节省出时间，在后面可以上完更多的课程。最终学习的课程数就是最多可以修读的课程数目。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        '''
        这题关键在于想明白总的 duration 和 last_day 是判断一个课程能不能上的关键，
        够一定能上，不够一定上不了，所以可以用用贪心减少总 duration，最大化课程数量。
        同时每考虑一个新的课程就尝试把它加到选课表中，短的优先，每一步的选择都是最优的，
        结果也自然是最优的。

        反向思维：不妨想象任意一个合法的选课表，其总时长一定是大于等于这个贪心算法的同课程数量的结果。不同于贪心算法选出来的课程一定可以用更优的课程替换掉。
        '''
        courses.sort(key=lambda c: c[1])  # 按照 last_day 从小到大排序

        h = []
        day = 0  # 已消耗时间
        for duration, last_day in courses:
            if day + duration <= last_day:  # 没有超过 last_day，直接学习
                day += duration
                heappush(h, -duration)  # 加负号变成最大堆
            elif h and duration < -h[0]:  # 该课程的时间比之前的最长时间要短 
                # 反悔，撤销之前 duration 最长的课程，改为学习该课程
                # 节省出来的时间，能在后面上完更多的课程
                day += heapreplace(h, -duration) + duration
        return len(h)