Leetcode: 630. Course Schedule III | 含C++笔记

思路：

我一开始看到这题，感觉他像可以用Greedy解法解的问题，然後又想他是III，所以他也可以用图呈现？

感觉需要先将课程依照期限，由小排到大。

後来查找了一下，感觉他像Activity Network （ PERT Network ）的问题。

所以这题的问题是：要怎麽用手中的现有资讯，组出一个合理的流程图？

因为没什麽思路，所以我就照Hint 1, Hint2做。

笔记:

想用2D vector的其中一个column进行排序的话，可以做一个custom sort。

    for (auto pair: courses) {
        cout << pair[0] << " " << pair[1] << ", ";
    }
    sort(courses.begin(), courses.end(), 
        [] (const vector<int> &coursea, const vector<int> &courseb)
        {
            return coursea[1] < courseb[1];
        });
    cout << endl;
    for (auto pair: courses) {
        cout << pair[0] << " " << pair[1] << ", ";
    }

程序码：

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), 
            [] (const vector<int> &coursea, const vector<int> &courseb)
             {
                 return coursea[1] < courseb[1];
             });

        int currentTotalTime = 0, count = 0;
        priority_queue<int> pq;
        
        for (auto pair: courses) {
            
            currentTotalTime += pair[0];
            pq.push(pair[0]);
            
            if (currentTotalTime <= pair[1])
                count++;
            else if((currentTotalTime > pair[1]) && !pq.empty()) {
                int curr_biggest = pq.top();
                currentTotalTime -= curr_biggest;
                pq.pop();    
            }
        }
        return count;
    }
};

後来

後来看Hint後有点回过味来，其实这题不需要安排流程图，只是要在有限时间内塞越多工作越好，所以遇到饱和的情况，就把比较肥的东西丢走，这样理论上就能容纳更多小的东西。

所以最後我就用heap(priority quequ)储存合理的工作内容，一但有超过的情况，就召唤最大值，把它删了。
　
　
参考：
https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
https://stackoverflow.com/questions/45494567/c-how-to-sort-the-rows-of-a-2d-vector-by-the-values-in-each-rows-column
https://leetcode.com/problems/course-schedule-iii/
https://yuihuang.com/cpp-stl-priority-queue/