[LeetCode] 630. Course Schedule III

轉自LeetCode

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dthday. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.

Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation: 
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

1. The integer 1 <= d, t, n <= 10,000.
2. You can't take two courses simultaneously.

<Solution>

想法如下

• 雖然是 207. Course Schedule 的衍生題，但已經是完全不同題目了

• 這題是要根據修課長度，和結束時間，來找出最多可以修課的數目

• 首先，一定是先修結束時間比較早的課。因為如果先修結束時間比較晚的課，那結束時間比較早的課就不一定能修，但如果先修結束時間比較早的課，還有可能可以修結束時間比較晚的課

• 用一個變數 time 來當作目前拿來修課的時間。如果下一堂課 courseN，是可以修的話，就代表 time + durationN <= end_dayN，這時候不用猶豫，直接修

• 如果下一堂課不能修，代表 time + durationN > end_dayN，這時候，回頭找之前修過的課中，duration 最長的那堂課且大於 durationN，把它拿掉，然後再加入 courseN 這堂課

• 為什麼要回頭找 duration 最長且大於 durationN 的課，並拿掉呢？用 durationMax 表示duration 最長且大於 durationN 的課的長度，因為 durationMax > durationN，所以拿掉 durationMax 一定保證 time + durationN < end_dayN，而且因為是拿掉最長的 duration，所以剩下的時間 durationMax - durationN 會是最大，讓我們更有可能可以修更多課。在實作上，可以用一個 PriorityQueue 來存

code 如下

Java(參考解法)

O(nlogn): for loop O(n) and max heapification O(logn)

Java

Kotlin