1203. 项目管理#

1
有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。
2

3
group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。
4

5
项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。
6

7
请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
8

9
同一小组的项目，排序后在列表中彼此相邻。
10
项目之间存在一定的依赖关系，
11

12
我们用一个列表 beforeItems 来表示，
13

14
其中 beforeItems[i] 表示在进行第 i 个项目前应该完成的所有项目。
15

16
如果存在多个解决方案，只需要返回其中任意一个即可。
17

18
如果没有合适的解决方案，就请返回一个 空列表 。
19

20

21

22
示例 1：
23

24

25
输入：
26

27
n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1],
28
beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
29

30
输出：[6,3,4,1,5,2,0,7]
31
示例 2：
32

33
输入：
34
n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1],
35
beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
36

37
输出：[]
38
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。
39

40

41
提示：
42

43
1 <= m <= n <= 3 * 104
44
group.length == beforeItems.length == n
45
-1 <= group[i] <= m - 1
46
0 <= beforeItems[i].length <= n - 1
47
0 <= beforeItems[i][j] <= n - 1
48
i != beforeItems[i][j]
49
beforeItems[i] 不含重复元素

1
class Solution {
2
public:
3
    vector<int> sortItems(
4
        int n, int m,
5
        vector<int>& group,
6
        vector<vector<int>>& beforeItems)
7
        {
8
        vector<int> ans, blank;
9
        //如果某个项目不属于当前任何小组，
10
        //新建一个小组，并且把它分给这个小组，为了避免冲突，新的小组编号从m开始
11
        for(int i = 0; i < group.size(); i++)
12
        if(group[i] == -1)
13
        {
14
            group[i] = m++;
15
        }
16

17
        //分别保存组间依赖关系、项目之间的依赖关系、各个小组负责的项目
18
        vector<int> topoGroup[m], topoItem[n], groupItem[m];
19
        //分别保存小组和项目在图中的入度
20
        int groupDgr[m], itemDgr[n];
21
        //避免添加多余的有向边，依赖关系只需要一条有向边就可以表示
22
        unordered_set<int> vis;
23
        memset(groupDgr, 0, sizeof groupDgr);
24
        memset(itemDgr, 0 ,sizeof itemDgr);
25
        for(int i = 0; i < beforeItems.size(); i++)
26
        {
27
            //将项目添加到对应的组内
28
            groupItem[group[i]].push_back(i);
29
            for(int j = 0; j < beforeItems[i].size(); j++)
30
            {
31
                //hashval用于判断是否有重复的有向边出现
32
                int u = beforeItems[i][j], hashval = group[u] * m + group[i];
33
                topoItem[u].push_back(i);
34
                itemDgr[i]++;
35
                //自己不能依赖自己
36
                if(group[i] == group[u] || vis.find(hashval) != vis.end()) continue;
37
                vis.insert(hashval);
38
                topoGroup[group[u]].push_back(group[i]);
39
                groupDgr[group[i]]++;
40
            }
41
        }
42

43
        //groupOrder保存了组的顺序
44
        vector<int> groupOrder;
45
        queue<int> q;
46
        for(int i = 0; i < m; i++)
47
        if(groupDgr[i] == 0) q.push(i);
48

49
        while(!q.empty())
50
        {
51
            int u = q.front();
52
            q.pop();
53
            groupOrder.push_back(u);
54
            for(int i = 0; i < topoGroup[u].size(); i++)
55
            {
56
                int v = topoGroup[u][i];
57
                groupDgr[v]--;
58
                if(groupDgr[v] == 0) q.push(v);
59
            }
60
        }
61

62
        //判断组内项目是否满足拓扑排序
63
        for(int i = 0; i < groupOrder.size(); i++)
64
        {
65
            int t = groupOrder[i];
66
            for(int j = 0; j < groupItem[t].size(); j++)
67
            {
68
                int u = groupItem[t][j];
69
                if(itemDgr[u] == 0) q.push(u);
70
            }
71

72
            int cnt = 0;
73
            while(!q.empty())
74
            {
75
                int u = q.front();
76
                q.pop();
77
                cnt++;
78
                ans.push_back(u);
79
                for(int j = 0; j < topoItem[u].size(); j++)
80
                {
81
                    int v = topoItem[u][j];
82
                    itemDgr[v]--;
83
                    if(itemDgr[v] == 0 && group[v] == t) q.push(v);
84
                }
85
            }
86
            if(cnt != groupItem[t].size()) return blank;
87
        }
88

89
        //如果组间关系不能满足拓扑排序，必定有项目不能加入ans内
90
        if(ans.size() != n) return blank;
91

92
        return ans;
93
    }
94
};