630 课程表 III（贪心）

系统管理员 2022-09-02 01:14 96阅读 0赞

**1. 问题描述：**

这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

**示例：**

输入: \[\[100, 200\], \[200, 1300\], \[1000, 1250\], \[2000, 3200\]\]  
输出: 3  
解释:  
这里一共有 4 门课程, 但是你最多可以修 3 门:  
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。  
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。  
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。  
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。

**提示:**

整数 1 <= d, t, n <= 10,000 。  
你不能同时修两门课程。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/course-schedule-iii

**2. 思路分析：**

分析题目可以知道这是一道**贪心**题目（贪心一般思路比较难想，证明过程也比较抽象），我们可以先从直觉上看怎么样选择这些课程能够完成更多的课程，首先我们应该选择那些截止时间尽可能短的这样能够完成更多的任务，所以首先需要按照截止时间的由小到大排序，然后我们可以按照两个规则选择当前的任务：

1.  选择的个数是最多的
2.  用时是最短的

首先我们应该选择个数最多的，也即能够选择当前任务的时候那么就选择当前的任务，当选择当前任务之后超过截止时间的时候那么我们应该去除掉1~i任务中的其中一个，这样才能够使得当前选择第i个任务是满足截止时间要求的，所以当不满足题目要求的时候我们应该去除掉的是其中一个任务所以总的个数为i - 1，并且我们在去除任务的时候应该尽可能使得去掉任务的持续时间是最长的，这样可以使得满足选择个数最多的情况下用时是最短的，这样才可以得到最优解。我们可以使用一个**大根堆**来维护到当前i个任务的持续时间，这样堆顶元素肯定是持续时间最大的那个，当我们发现加入当前任务之后超过了截止时间那么就应该去除掉堆顶元素，这样一定是满足题目要求的。

**3. 代码如下：**

from typing import List
    import heapq
    
    
    class Solution:
        def scheduleCourse(self, courses: List[List[int]]) -> int:
            courses.sort(key=lambda x: (x[1], x[0]))
            s = 0
            # 使用列表来存储大根堆中的元素
            heap = list()
            for i in range(len(courses)):
                # 一开始的时候先加入第i个任务这样可以保证题目是有解的, 因为前i个任务是满足题目要求的所以我们可以删掉当前的任务那么肯定也是满足要求的
                s += courses[i][0]
                # 堆中的元素值为负这样可以表示大根堆, python中只有小根堆
                heapq.heappush(heap, -courses[i][0])
                # 说明用时是大于截止时间的那么就应该去掉持续时间最大的那个任务, 也即堆顶元素
                if s > courses[i][1]:
                    s -= -heapq.heappop(heap)
            return len(heap)