2020-06-09

1.題目描述

項目管理

2.題解

由于題目要求同一小組的項目，排序后在列表中彼此相鄰 1.首先進行組間排序，有拓撲序列則轉向2 2.其次進行組內排序，有拓撲序列則輸出結果

3.代碼

class Solution { public:vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {// n個項目，m個小組if (m==0||n==0) return vector<int>();int grouplen=m;for (int i=0;i<group.size();i++){ // 沒有組的重新進行分組if (group[i]==-1) group[i]=grouplen++;}vector<int> itemdegree(n);vector<vector<int>> itemadjacent(n);vector<int> groupdegree(grouplen);vector<vector<int>> groupadjacent(grouplen);vector<vector<int>> groupitem(grouplen);// 進行初始化for (int i=0;i<beforeItems.size();i++){for (auto index:beforeItems[i]){ if (group[i]==group[index]){ // 組內的關系itemdegree[i]++;itemadjacent[index].push_back(i);}else{if (!count(groupadjacent[group[index]].begin(),groupadjacent[group[index]].end(),group[i])){groupdegree[group[i]]++;groupadjacent[group[index]].push_back(group[i]);}} }}for (int i=0;i<group.size();i++){groupitem[group[i]].push_back(i);}vector<int> vec;// 先處理組間關系queue<int> que1;int cnt1=0;for (int i=0;i<grouplen;i++){if (!groupdegree[i]){ // 入度為0que1.push(i);vec.push_back(i);cnt1++;}}while (!que1.empty()){int tmp=que1.front();que1.pop();for (auto value:groupadjacent[tmp]){groupdegree[value]--;if (!groupdegree[value]){que1.push(value);vec.push_back(value);cnt1++;}}}// 組間關系不滿足條件if (cnt1!=grouplen) return vector<int>();vector<int> res;// 再處理組內關系for (int i=0;i<grouplen;i++){int groupindex=vec[i]; // 先處理第groupindex組queue<int> que2;int cnt2=0;for (auto value:groupitem[groupindex]){if (!itemdegree[value]){que2.push(value);res.push_back(value);cnt2++;}}while (!que2.empty()){int tmp=que2.front();que2.pop();for (auto value:itemadjacent[tmp]){itemdegree[value]--;if (!itemdegree[value]){que2.push(value);res.push_back(value);cnt2++;}}}if (cnt2!=groupitem[groupindex].size()) return vector<int>();}return res;} };

總結

以上是生活随笔為你收集整理的1203. 项目管理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。