Description Link to heading

2050. Parallel Courses III (Hard)

Solution Link to heading

The approach to this problem is quite evident, and it requires the utilization of topological sorting. During the process oftopological sorting, the longest required time should be calculated.

Code Link to heading 

class Solution {
  public:
    int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
        vector<int> cnt(n + 1);
        vector<unordered_set<int>> next(n + 1);
        for (auto &vec : relations) {
            ++cnt[vec[1]];
            next[vec[0]].insert(vec[1]);
        }
        queue<int> zero;
        // vector<int> res;
        vector<int> ans(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (cnt[i] == 0) {
                zero.push(i);
                ans[i] = time[i - 1];
            }
        }
        int total = 0;
        while (!zero.empty()) {
            int idx = zero.front();
            // res.push_back(idx);
            total = max(total, ans[idx]);
            zero.pop();
            for (int course : next[idx]) {
                ans[course] = max(ans[course], ans[idx] + time[course - 1]);
                if (--cnt[course] == 0) {
                    zero.push(course);
                }
            }
        }
        return total;
    }
};```