630.md

630 Course Schedule III

Description

link

---

Solution

• 树和DFS
• Greedy和heap也是非常好的搭档

基本贪心的思路就是，按照能满足题目的条件对数组或者队列进行排序，然后使用堆（最常见）或者其他能够保证贪心循环的数据结构来存储答案

回到此题：

1. 首先根据结束日期进行排序，得到的结果都是按照end date排序好的
2. �循环排序好的数组，当前start设置为上一次添加答案后更新的start，将当前start加上当前t作为最新start
3. 将当前需要时间入堆（最大堆）
4. 如果更新后的start大于当前课程的end，说明不满足时间要求，去掉答案中耗时最多的课程（这里最多去掉一节，具体可以细品）
5. heap的长度就是结果

这题的堆的作用就是用来保持随时能找到需要去掉的课程，因为根据贪心算法，每有课程进来导致不满足条件，必然可以去掉其中最大cost的课程来保证结果正确，注意时刻更新start，保证当前消耗正确

---

Code

Complexity T : O(n(log(n))

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses = sorted(courses, key=lambda x: x[1])
        pq = []
        start = 0
        for t, end in courses:
            start += t
            heapq.heappush(pq, -t)
            if start > end:
                start += heapq.heappop(pq)
        return len(pq)