630.课程表III

原题

一、贪心

先根据「结束时间」对 coursescourses 排升序，从前往后考虑每个课程，处理过程中维护一个总时长 sumsum，对于某个课程 courses[i]courses[i] 而言，根据如果学习该课程，是否满足「最晚完成时间」要求进行分情况讨论：

1. 学习该课程后，满足「最晚完成时间」要求，即 sum + courses[i][0] <= courses[i][1]，则进行学习；

2. 学习该课程后，不满足「最晚完成时间」要求，此时从过往学习的课程中找出「持续时间」最长的课程进行「回退」操作（这个持续时长最长的课程有可能是当前课程）。

import heapq
#py没有大根堆。存入负值，用小根堆实现大根堆
class BigHeap:
    def __init__(self):
        self.arr = list()
    #建堆
    def heapify(self):
        heapq.heapify(self.arr)
    #插入
    def insert(self, val):
        heapq.heappush(self.arr, -val)   # 存入负值
    #弹出
    def pop(self):
        val = heapq.heappop(self.arr)
        # 先取出再转负
        return -val
    #返回堆顶
    def getTop(self):
        if not self.arr:
            return
        return -self.arr[0]
    #判断堆空
    def isEmpty(self):
        return not self.arr
    #返回堆大小
    def size(self):
        return len(self.arr)

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key = lambda x : x[1])
        sum = 0
        heap = BigHeap()
        for duration, lastDay in courses:
            sum += duration
            heap.insert(duration)
            if sum > lastDay:
                sum -= heap.pop()
        return heap.size()