文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

公司共有 n 個項目和 m 個小組，每個項目要不無人接手，要不就由 m 個小組之一負(fù)責(zé)。

group[i] 表示第 i 個項目所屬的小組，如果這個項目目前無人接手，那么 group[i] 就等于 -1。（項目和小組都是從零開始編號的）小組可能存在沒有接手任何項目的情況。

請你幫忙按要求安排這些項目的進度，并返回排序后的項目列表：

• 同一小組的項目，排序后在列表中彼此相鄰。
• 項目之間存在一定的依賴關(guān)系，我們用一個列表 beforeItems 來表示，其中 beforeItems[i] 表示在進行第 i 個項目前（位于第 i 個項目左側(cè)）應(yīng)該完成的所有項目。

如果存在多個解決方案，只需要返回其中任意一個即可。
如果沒有合適的解決方案，就請返回一個 空列表 。

示例 1：

輸入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] 輸出：[6,3,4,1,5,2,0,7] 示例 2：輸入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] 輸出：[] 解釋：與示例 1 大致相同，但是在排序后的列表中，4 必須放在 6 的前面。提示： 1 <= m <= n <= 3 * 10^4 group.length == beforeItems.length == n -1 <= group[i] <= m - 1 0 <= beforeItems[i].length <= n - 1 0 <= beforeItems[i][j] <= n - 1 i != beforeItems[i][j] beforeItems[i] 不含重復(fù)元素

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

拓?fù)渑判驅(qū)W習(xí)、及相關(guān)題目

• 兩次拓?fù)渑判蚣纯?/li>

class Solution { public:vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {for(int i = 0; i < n; i++){if(group[i] == -1)group[i] = m++;//無人接管的分配一個虛擬團隊號}vector<vector<int>> itemgraph(n);vector<vector<int>> groupgraph(m);vector<int> itemIndegree(n, 0);vector<int> groupIndegree(m, 0);for(int i = 0; i < n; i++){for(auto j : beforeItems[i]){itemgraph[j].push_back(i);//建圖itemIndegree[i]++;//記錄出入度if(group[i] != group[j]) // 注意條件{ // 團隊也建圖，記錄出入度groupgraph[group[j]].push_back(group[i]);groupIndegree[group[i]]++;}}}vector<vector<int>> g_items(m);// item 拓?fù)渑判?/span>queue<int> q;for(int i = 0; i < n; i++)if(itemIndegree[i] == 0)q.push(i);int countItem = 0;while(!q.empty()){int i = q.front();q.pop();countItem++;g_items[group[i]].push_back(i);//每個item順序存入自己的團隊for(auto j : itemgraph[i]){if(--itemIndegree[j]==0)q.push(j);}}if(countItem != n)return {};// 團隊拓?fù)渑判?/span>vector<int> g_order;for(int i = 0; i < m; i++)if(groupIndegree[i] == 0)q.push(i);int countgroup = 0;while(!q.empty()){int g = q.front();q.pop();countgroup++;g_order.push_back(g);for(auto j : groupgraph[g]){if(--groupIndegree[j]==0)q.push(j);}}if(countgroup != m)return {};// 寫入答案vector<int> ans(n);int idx = 0;for(auto g : g_order){for(auto i : g_items[g])ans[idx++] = i;}return ans;} };

200 ms 43 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1203. 项目管理（两次拓扑排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。