本文共 10927 字,大约阅读时间需要 36 分钟。
PS:算法并非原创,仅作个人学习记录使用,侵删
题目描述
算法分析
一开始看到这类项目时间安排的题目,我就想起来算法里面的贪心算法。但是仔细想想,贪心算法涉及到具体的时间,且项目之间没有依赖关系。而这里的项目之间存在明显的依赖关系,于是我又想起了拓扑排序,也就是将项目作为结点,依赖关系作为边,建立有向图,然后根据有向图得出拓扑排序的序列。如果图中出现环,则说明排序无解。代码实现
【C】/*算法思想:拓扑排序*/int* topSort(int* returnSize, int* deg, int** graph, int* graphColSize, int* items, int itemsSize) { //返回数组大小:returnSize,项目的承办组:deg,图的邻接矩阵:graph,图的每行大小:graphColSize,项目数组:items,项目数目:itemsSize *returnSize = 0;//返回数组大小一开始为0 int Q[itemsSize]; int left = 0, right = 0; for (int i = 0; i < itemsSize; i++) { //遍历项目 if (deg[items[i]] == 0) { //如果项目无人接管。 Q[right++] = items[i]; } } int* res = malloc(sizeof(int) * itemsSize); while (left < right) { int u = Q[left++]; res[(*returnSize)++] = u; for (int i = 0; i < graphColSize[u]; i++) { int v = graph[u][i]; if (--deg[v] == 0) { Q[right++] = v; } } } if (*returnSize == itemsSize) { return res; } *returnSize = 0; return NULL;}int* sortItems(int n, int m, int* group, int groupSize, int** beforeItems, int beforeItemsSize, int* beforeItemsColSize, int* returnSize) { int* groupItem[n + m]; int groupItemColSize[n + m]; int groupItemColCapacity[n + m]; for (int i = 0; i < n + m; i++) { groupItem[i] = malloc(sizeof(int)); groupItemColSize[i] = 0; groupItemColCapacity[i] = 0; } // 组间和组内依赖图 int* groupGraph[n + m]; int groupGraphColSize[n + m]; int groupGraphColCapacity[n + m]; for (int i = 0; i < n + m; i++) { groupGraph[i] = malloc(sizeof(int)); groupGraphColSize[i] = 0; groupGraphColCapacity[i] = 0; } int* itemGraph[n]; int itemGraphColSize[n]; int itemGraphColCapacity[n]; for (int i = 0; i < n; i++) { itemGraph[i] = malloc(sizeof(int)); itemGraphColSize[i] = 0; itemGraphColCapacity[i] = 0; } // 组间和组内入度数组 int groupDegree[n + m]; memset(groupDegree, 0, sizeof(groupDegree)); int itemDegree[n]; memset(itemDegree, 0, sizeof(itemDegree)); int id[n + m]; for (int i = 0; i < n + m; ++i) { id[i] = i; } int leftId = m; // 给未分配的 item 分配一个 groupId for (int i = 0; i < n; ++i) { if (group[i] == -1) { group[i] = leftId++; } if (groupItemColSize[group[i]] == groupItemColCapacity[group[i]]) { int* x = &groupItemColCapacity[group[i]]; *x = (*x) ? (*x) * 2 : 1; groupItem[group[i]] = realloc(groupItem[group[i]], sizeof(int) * (*x)); } groupItem[group[i]][groupItemColSize[group[i]]++] = i; } // 依赖关系建图 for (int i = 0; i < n; ++i) { int curGroupId = group[i]; for (int j = 0; j < beforeItemsColSize[i]; j++) { int item = beforeItems[i][j]; int beforeGroupId = group[item]; if (beforeGroupId == curGroupId) { itemDegree[i]++; if (itemGraphColSize[item] == itemGraphColCapacity[item]) { int* x = &itemGraphColCapacity[item]; (*x) = (*x) ? (*x) * 2 : 1; itemGraph[item] = realloc(itemGraph[item], sizeof(int) * (*x)); } itemGraph[item][itemGraphColSize[item]++] = i; } else { groupDegree[curGroupId]++; if (groupGraphColSize[beforeGroupId] == groupGraphColCapacity[beforeGroupId]) { int* x = &groupGraphColCapacity[beforeGroupId]; (*x) = (*x) ? (*x) * 2 : 1; groupGraph[beforeGroupId] = realloc(groupGraph[beforeGroupId], sizeof(int) * (*x)); } groupGraph[beforeGroupId][groupGraphColSize[beforeGroupId]++] = curGroupId; } } } // 组间拓扑关系排序 int groupTopSortSize; int* groupTopSort = topSort(&groupTopSortSize, groupDegree, groupGraph, groupGraphColSize, id, n + m); if (groupTopSortSize == 0) { *returnSize = 0; return NULL; } int* ans = malloc(sizeof(int) * groupTopSortSize); *returnSize = 0; // 组内拓扑关系排序 for (int i = 0; i < groupTopSortSize; i++) { int curGroupId = groupTopSort[i]; int size = groupItemColSize[curGroupId]; if (size == 0) { continue; } int resSize; int* res = topSort(&resSize, itemDegree, itemGraph, itemGraphColSize, groupItem[curGroupId], groupItemColSize[curGroupId]); if (resSize == 0) { *returnSize = 0; return NULL; } for (int j = 0; j < resSize; j++) { ans[(*returnSize)++] = res[j]; } } return ans;}【C++】
/*算法思想:拓扑排序*/class Solution { public: vector sortItems(int n, int m, vector & group, vector>& beforeItems) { for(int i = 0; i < n; i++){ //遍历项目 if(group[i] == -1) group[i] = m++;//无人接管的分配一个虚拟团队号 } vector > itemgraph(n); vector > groupgraph(m); vector itemIndegree(n, 0); vector 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 > g_items(m); // item 拓扑排序 queue 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 { }; // 团队拓扑排序 vector 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 ans(n); int idx = 0; for(auto g : g_order){ for(auto i : g_items[g]) ans[idx++] = i; } return ans; }};
【java】
class Solution { public int[] sortItems(int n, int m, int[] group, List【python】
> beforeItems) { List
> groupItem = new ArrayList
>(); for (int i = 0; i < n + m; ++i) { groupItem.add(new ArrayList ()); } // 组间和组内依赖图 List
> groupGraph = new ArrayList
>(); for (int i = 0; i < n + m; ++i) { groupGraph.add(new ArrayList ()); } List
> itemGraph = new ArrayList
>(); for (int i = 0; i < n; ++i) { itemGraph.add(new ArrayList ()); } // 组间和组内入度数组 int[] groupDegree = new int[n + m]; int[] itemDegree = new int[n]; List id = new ArrayList (); for (int i = 0; i < n + m; ++i) { id.add(i); } int leftId = m; // 给未分配的 item 分配一个 groupId for (int i = 0; i < n; ++i) { if (group[i] == -1) { group[i] = leftId; leftId += 1; } groupItem.get(group[i]).add(i); } // 依赖关系建图 for (int i = 0; i < n; ++i) { int curGroupId = group[i]; for (int item : beforeItems.get(i)) { int beforeGroupId = group[item]; if (beforeGroupId == curGroupId) { itemDegree[i] += 1; itemGraph.get(item).add(i); } else { groupDegree[curGroupId] += 1; groupGraph.get(beforeGroupId).add(curGroupId); } } } // 组间拓扑关系排序 List groupTopSort = topSort(groupDegree, groupGraph, id); if (groupTopSort.size() == 0) { return new int[0]; } int[] ans = new int[n]; int index = 0; // 组内拓扑关系排序 for (int curGroupId : groupTopSort) { int size = groupItem.get(curGroupId).size(); if (size == 0) { continue; } List res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId)); if (res.size() == 0) { return new int[0]; } for (int item : res) { ans[index++] = item; } } return ans; } public List topSort(int[] deg, List
> graph, List items) { Queue queue = new LinkedList (); for (int item : items) { if (deg[item] == 0) { queue.offer(item); } } List res = new ArrayList (); while (!queue.isEmpty()) { int u = queue.poll(); res.add(u); for (int v : graph.get(u)) { if (--deg[v] == 0) { queue.offer(v); } } } return res.size() == items.size() ? res : new ArrayList (); }}
class Solution: def sortItems(self, n, m, group, beforeItems): # 构建组到任务的映射 group2Items = collections.defaultdict(set) index = m for i in range(n): if group[i] == -1: group[i] = index group2Items[index] = set([i]) index += 1 else: group2Items[group[i]].add(i) # 构建组的拓扑图 beforeGroupsDic, preGroupsDic = { }, { } for i in range(index): beforeGroupsDic[i] = set() preGroupsDic[i] = set() for i in range(n): for j in beforeItems[i]: beforeGroupsDic[group[i]].add(group[j]) preGroupsDic[group[j]].add(group[i]) # 去除组内部的节点 如果存在环,在任务级别判断 for i in range(index): if i in beforeGroupsDic[i]: beforeGroupsDic[i].remove(i) preGroupsDic[i].remove(i) res = [] while beforeGroupsDic: # 找出所有入度为0的小组 groups = [key for key, values in beforeGroupsDic.items() if not beforeGroupsDic[key]] if not groups: return [] # 处理小组的拓扑关系 for g in groups: beforeGroupsDic.pop(g) for g1 in preGroupsDic[g]: beforeGroupsDic[g1].remove(g) preGroupsDic.pop(g) # 对小组内部建立拓扑图 for key in groups: its = list(group2Items[key]) # 对这些点建立拓扑图 beforeItemsDic, preItemsDic = { }, { } for i in its: beforeItemsDic[i] = set() preItemsDic[i] = set() for i in its: for j in beforeItems[i]: if group[i] == group[j]: beforeItemsDic[i].add(j) preItemsDic[j].add(i) while beforeItemsDic: items = [k for k, v in beforeItemsDic.items() if not beforeItemsDic[k]] if not items: return [] res += items # 处理项目的拓扑关系 for item in items: beforeItemsDic.pop(item) for item1 in preItemsDic[item]: if item1 in beforeItemsDic: beforeItemsDic[item1].remove(item) preItemsDic.pop(item) return res
转载地址:http://aquv.baihongyu.com/