sns社交网站 建设,房产中介网站怎么做,淘宝导购网站备案,曲靖做网站建设的公司公司共有 n 个项目和 m 个小组#xff0c;每个项目要不无人接手#xff0c;要不就由 m 个小组之一负责。
group[i] 表示第 i 个项目所属的小组#xff0c;如果这个项目目前无人接手#xff0c;那么 group[i] 就等于 -1。#xff08;项目和小组都是从零开始编号的#xf…公司共有 n 个项目和 m 个小组每个项目要不无人接手要不就由 m 个小组之一负责。
group[i] 表示第 i 个项目所属的小组如果这个项目目前无人接手那么 group[i] 就等于 -1。项目和小组都是从零开始编号的小组可能存在没有接手任何项目的情况。
请你帮忙按要求安排这些项目的进度并返回排序后的项目列表
同一小组的项目排序后在列表中彼此相邻。 项目之间存在一定的依赖关系我们用一个列表 beforeItems 来表示其中 beforeItems[i] 表示在进行第 i 个项目前位于第 i 个项目左侧应该完成的所有项目。 如果存在多个解决方案只需要返回其中任意一个即可。如果没有合适的解决方案就请返回一个 空列表 。
示例 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]
代码
class Solution {public int[] sortItems(int n, int m, int[] group, ListListInteger beforeItems) {ListListInteger groupItemsnew ArrayList();//组-项目的映射ListInteger groupIdnew ArrayList();//组的idListListInteger groupEdgesnew ArrayList();//组-组的图for(int i0;inm;i){groupItems.add(new ArrayList());groupId.add(i);groupEdges.add(new ArrayList());}ListListInteger itemEdgesnew ArrayList();//项目-项目int lastGroupm;for(int j0;jn;j)//构造 组和项目之间的映射关系{itemEdges.add(new ArrayList());if(group[j]-1)//无人接收的项目放在id序列的最后n个并且假设其有一个组接收{group[j]lastGroup;lastGroup;}groupItems.get(group[j]).add(j);}int[] itemDegreenew int[n];//对于每个项目的入度表int[] groupDegreenew int[mn];//对于每个组的入度表for(int k0;kbeforeItems.size();k)//根据先后关系构造组-组图 以及项目-项目的图{int curgroup[k];for(int j0;jbeforeItems.get(k).size();j){int itembeforeItems.get(k).get(j);if(group[item]cur)//同一个组负责的项目就加入项目-项目图{itemDegree[k];itemEdges.get(item).add(k);}else{//不是同一个组负责的项目就加入组-组图{groupDegree[cur];groupEdges.get(group[item]).add(cur);}}}ListInteger groupSorttoSort(groupDegree,groupEdges,groupId);//先对组——组图进行拓扑排序if(groupSort.size()0) return new int[0];ListInteger ansnew ArrayList();for(int c:groupSort)//再对每个组组内的项目进行拓扑排序{if(groupItems.get(c).size()0) continue;ListInteger intoSort(itemDegree,itemEdges,groupItems.get(c));if(in.size()0)return new int[0];ans.addAll(in);}return ans.stream().mapToInt(Integer::intValue).toArray();}public ListInteger toSort(int[] degree,ListListInteger edges,ListInteger point){//拓扑排序代码ListInteger resnew ArrayList();QueueInteger queuenew LinkedList();for(Integer integer:point){if(degree[integer]0)queue.offer(integer);}while (!queue.isEmpty()){int tqueue.poll();ListInteger listedges.get(t);for(int c:list){degree[c]--;if(degree[c]0)queue.offer(c);}res.add(t);}return res.size()point.size()?res:new ArrayList();}
}
