主題

[LeetCode] 2050. Parallel Courses III

Mmry | 2023-10-18 09:17:25 | 巴幣 0 | 人氣 73

2023 / 10 / 18 Daily Problem

題目說明 :

給定 n 個課程，每個課程有各自所需完成的時間，並且課程之間有先後順序(擋修的概念)，找出最少要花多少時間才能將所有課程修完。

思考過程 :

選擇課程的原則為: 1. 已經修過先修課程 2. 無需要先修課程。

假設目前有個課程C，需要兩個先修課程A以及B，所花費時間至少為 max(A,B) + C。若有三個以上同理。

因此每次修課，我們僅挑選indegree等於0的課程，並將下堂課(就是先修課程的相反)的 indegree-1，必且去更新下堂課最少所需花費的時間。

如果下堂課的indegree等於0，代表先修課程我們皆已完成，納入queue中繼續計算，畢竟該課程可能是別堂課的先修課。

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> nxt(n+1);
        vector<int> indegree(n+1, 0);

        for(auto r : relations){
            int pre = r[0], aft = r[1];
            nxt[pre].push_back(aft);
            indegree[aft]++;
        }

        queue<int> q;
        vector<int> leastFinishTime(n+1);
        for(int i=1;i<=n;i++){
            if(indegree[i] == 0){
                leastFinishTime[i] = time[i-1];
                q.push(i);
            }
        }

        int ret = 0;
        while(!q.empty()){
            int course = q.front(); q.pop();
             ret = max(ret, leastFinishTime[course]);

            for(int i=0;i<nxt[course].size();i++){
                int nxtCourse = nxt[course][i];
                leastFinishTime[nxtCourse] = max(leastFinishTime[course] + time[nxtCourse-1], leastFinishTime[nxtCourse]);
                indegree[nxtCourse]--;

                if(indegree[nxtCourse]==0){
                    q.push(nxtCourse);
                }
            }
        }

        return ret;
    }
};