# 【LeetCode】630. Course Schedule III

## 前言
此題的連結 [LeetCode 630. Course Schedule III](https://leetcode.com/problems/course-schedule-iii/)
我的方法並不是最好的方法，PR 5%而已，但這個方法適合正在初學演算法的人參考，練習自己想出演算法。

## 想法
因為要找到最好的課來上，就必須定義甚麼是最好的課？
## 定義最好的課
可以確定的是，假設我想要上最多的課，其中一個條件是，最快結束的課，我就要先上。
I have to choos those courses which are most close deadline.
例如：[100,200], [200,400]，那我必須先選[100,200]因為這門課的截止時間比較早。
所以第一步驟：
> 先把所有的課照著截止時間由小排到大(由近排到遠)

接下來，只需要去判斷當我加入下一個課時，會不會超過他的截止時間就好。

if (now + courses[i][0] <= courses[i][1]){
    now+=courses[i][0];
    pq.push(courses[i][0]);
}

此時，我們會發現問題。
舉例：[5,5],[4,6],[2,6]
照現在的想法會只有[5,5]這堂課被上到，後面兩門後都無法。
所以就必須想一個辦法，使得程式在選完[5,5]後，能夠自己判斷選擇[4,6]或是[2,6]是優於[5,5]的。

## 想一個辦法
那麼實際上，就只需要去判斷上一個選的和現在要選的，有沒有比較好？
比較好的意思是
> 如果我現在選的這個能夠讓我有比上一個有更多的時間去修其他的課，那我就捨棄上一個選的，選擇現在這一個。

這個方法看似很對，但還差了一點點。
而且在寫這一個想法時，還要去注意第0個的情況，舉例：[3,2],[4,3]才不會造成Runtime Error。
寫完後，又會發現，在比對的時候，不是現在這一個跟前一個做比較，而是要現在這一個，跟前面所有的去做比較。

## 如何比較
為甚麼可以跟前面所有的做比較？
是因為前面的選擇都是照時間順序排，能夠保持**連續**的性質，跟前面所有的做完比較後，才能夠選擇出真正最好的組合。
那要用甚麼方式？
> 對於選過的課，把所花費的時間由大到小排序，若現在選擇的課可以讓我總時長變短，那我就把最長的刪掉，替換成現在要上的。

這個方式可以用**priority_queue**達成

## 使用priority_queue
priority_queue是一個能夠自動把加入的東西由大到小排序的佇列。
用法就跟STL中的queue一樣

- ```pq.push(var)``` 把值放進queue裡面，會自動排序
- ```pq.pop()``` 把最大的值從queue中刪除
- ```pq.top()``` 回傳最大值
- ```pq.size()``` 回傳有多少東西在queue裡面
- ```pq.empty()``` 回傳1或0，1代表沒東西，0代表還有東西

## 完整程式碼

class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
priority_queue<int> pq;
sort(courses.begin(),courses.end(),cmp);
int now = 0;
for (int i=0;i<courses.size();i++){
if (now + courses[i][0] <= courses[i][1]){
now+=courses[i][0];
pq.push(courses[i][0]);
}
else{
if (!pq.empty() && courses[i][0] < pq.top()){
now-=pq.top();
now+=courses[i][0];
pq.pop();
pq.push(courses[i][0]);
}
}
}
return pq.size();

}
static bool cmp(vector<int> a, vector<int> b){
return a[1] < b[1];
}
};

###### tags: `LeetCode` `程式`