题目描述
There are n
items each belonging to zero or one of m
groups where group[i]
is the group that the i
-th item belongs to and it’s equal to -1
if the i
-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.
Return a sorted list of the items such that:
- The items that belong to the same group are next to each other in the sorted list.
- There are some relations between these items where
beforeItems[i]
is a list containing all the items that should come before thei
-th item in the sorted array (to the left of thei
-th item).
Return any solution if there is more than one solution and return an empty list if there is no solution.
Example 1:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]
Example 2:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
Output: []
Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.
Constraints:
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]
does not contain duplicates elements.
算法1
(拓扑排序)
题意:公司共有 n
个项目和 m
个小组,每个项目要不没有归属,要不就由其中的一个小组负责。
我们用 group[i]
代表第i
个项目所属的小组,如果这个项目目前无人接手,那么 group[i]
就等于 -1。(项目和小组都是从零开始编号的)。请你帮忙按要求安排这些项目的进度,并返回排序后的项目列表:
同一小组的项目,排序后在列表中彼此相邻。
项目之间存在一定的依赖关系,我们用一个列表 beforeItems
来表示,其中 beforeItems[i]
表示在进行第i
个项目前(位于第i
个项目左侧)应该完成的所有项目。
结果要求:
如果存在多个解决方案,只需要返回其中任意一个即可。
如果没有合适的解决方案,就请返回一个 空列表。
题解:这道题属于比较复杂的拓扑排序,我们可以先通过对所有的组进行拓扑排序来判断所有的组之间有没有冲突,如果没有冲突的话,我们按照组的拓扑序,对每一组内部的项目进行拓扑排序。
- 首先为了方便起见,我们将所有无人认领的小组分配一个组号,这个组内只有这一个项目。
- 接下来我们统计一下每个组之间边关系和入度,因为是统计组之间的,所有组内依赖我们暂时不考虑,我们还需要考虑的是如果两个组之间有多条边,我们只计算一次。
- 同时,我们可以统计每一个组内部的边关系和入度,因为是统计组内的,所以组间依赖关系我们暂时不考虑。
- 我们对组进行拓扑排序,看一下是否有冲突,如果有冲突就返回,否则继续。
- 我们按照组的拓扑序,对每一个组内部进行拓扑排序。
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
vector<int> group_res,item_res;
unordered_map<int,set<int>> group_to_item_hash;
// 给每个无人领导的小组分配一个组号,同时使用哈希表统计每一个组内有多少项目。
for(int i = 0 ; i < n ; i ++)
{
if(group[i] == -1)
group[i] = m ++;
group_to_item_hash[group[i]].insert(i);
}
// 统计每个组的组间入度,统计每个组的组内项目入度
int group_ord[m] = {},item_ord[n] = {};
// 统计从每个组是哪些组的前驱关系,每个项目是哪些组内项目的前驱关系。
vector<set<int>> graph(m),item_graph(n);
for(int i = 0 ; i < n ; i ++)
{
if(beforeItems[i].size() == 0) continue;
for(auto pre : beforeItems[i])
{
if(group[pre] != group[i])
{
if(graph[group[pre]].count(group[i])== 0)
{
graph[group[pre]].insert(group[i]);
group_ord[group[i]] ++;
}
}else{
item_graph[pre].insert(i);
item_ord[i] ++;
}
}
}
queue<int> q;
for(int i = 0 ; i < m ; i ++)
if(group_ord[i] == 0)
q.push(i);
while(!q.empty())
{
int p = q.front();
q.pop();
group_res.push_back(p);
for(auto next : graph[p])
{
group_ord[next] --;
if(group_ord[next] == 0)
q.push(next);
}
}
if(group_res.size() != m) return {};
for(auto group_id : group_res)
{
queue<int> q;
for(auto item_id : group_to_item_hash[group_id])
if(item_ord[item_id] == 0)
q.push(item_id);
int cnt = 0;
while(!q.empty())
{
int p = q.front();
q.pop();
item_res.push_back(p);
cnt ++;
for(auto next : item_graph[p])
{
item_ord[next] -- ;
if(item_ord[next] == 0)
q.push(next);
}
}
if(cnt != group_to_item_hash[group_id].size())
return {};
}
return item_res;
}
};