這里有 n 門不同的在線課程，按從 1 到 n 編號(hào)。給你一個(gè)數(shù)組 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 門課將會(huì) 持續(xù) 上 durationi 天課，并且必須在不晚于 lastDayi 的時(shí)候完成。

你的學(xué)期從第 1 天開(kāi)始。且不能同時(shí)修讀兩門及兩門以上的課程。
返回你最多可以修讀的課程數(shù)目。

示例 1：
輸入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
輸出：3
解釋：
這里一共有 4 門課程，但是你最多可以修 3 門：
首先，修第 1 門課，耗費(fèi) 100 天，在第 100 天完成，在第 101 天開(kāi)始下門課。
第二，修第 3 門課，耗費(fèi) 1000 天，在第 1100 天完成，在第 1101 天開(kāi)始下門課程。
第三，修第 2 門課，耗時(shí) 200 天，在第 1300 天完成。
第 4 門課現(xiàn)在不能修，因?yàn)閷?huì)在第 3300 天完成它，這已經(jīng)超出了關(guān)閉日期。

示例 2：
輸入：courses = [[1,2]]
輸出：1

示例 3：
輸入：courses = [[3,2],[4,3]]
輸出：0

提示=
1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104
leetcode 630
思路：
可以用貪心法的思路來(lái)做，
1.假如有兩門課 (t1, d1) 和 (t2, d2)，假如 d1 <= d2，我們應(yīng)該先學(xué)前者，再學(xué)后者，這樣總的課程數(shù)是最優(yōu)的
2.根據(jù)1，我們可以把課程根據(jù) lastDay 從小到大排序，當(dāng)遍歷到 (ti，di) 課程時(shí)，如果學(xué) ti 課程，總時(shí)間超過(guò)了 di, 我們需要從已經(jīng)打算學(xué)的課程列表里面挑選出 duration 最大的課程和 ti 比較，如果 duration > ti, 則 duration 課程出列，ti 入列(減少 總 duration 的上限)，最后課程列表(可用最大值堆來(lái)實(shí)現(xiàn))的長(zhǎng)度即為最長(zhǎng)的課程數(shù)。文章來(lái)源地址http://www.zghlxwxcb.cn/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:     ### 過(guò)濾掉 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])  ### 默認(rèn)是最小值堆, 加負(fù)號(hào)變成最大值堆
        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)

到了這里，關(guān)于leetcode 630. 課程表 III的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！