本文共 7333 字，大约阅读时间需要 24 分钟。
项目时间安排的解决方案
项目时间安排问题可以通过拓扑排序来解决。在传统的贪心算法中，项目之间没有明确的依赖关系，这种方法并不适用。但当项目间存在明确的依赖关系时，我们可以将其建模为有向图，通过拓扑排序来确定项目的执行顺序。
拓扑排序的基本思想是：
以下是基于C语言的拓扑排序实现代码：
int* topSort(int* returnSize, int* deg, int** graph, int* graphColSize, int* items, int itemsSize) { *returnSize = 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;} 拓扑排序的核心逻辑包括：
在实际项目中，我们还需要处理组间依赖关系。这可以通过将项目分为不同的组，并为每个组生成一个独立的拓扑排序。具体实现步骤如下：
以下是C++语言的实现代码：
class Solution { vector sortItems(int n, int m, vector & group, const vector >& beforeItems) { vector groupItem(n + m); vector groupItemColSize(n + m); vector groupItemColCapacity(n + m); for (int i = 0; i < n + m; i++) { groupItem[i] = i; groupItemColSize[i] = 0; groupItemColCapacity[i] = 0; } vector groupGraph(n + m); vector groupGraphColSize(n + m); vector groupGraphColCapacity(n + m); for (int i = 0; i < n + m; i++) { groupGraph[i] = new int; groupGraphColSize[i] = 0; groupGraphColCapacity[i] = 0; } vector itemGraph(n); vector itemGraphColSize(n); vector itemGraphColCapacity(n); for (int i = 0; i < n; i++) { itemGraph[i] = new int; itemGraphColSize[i] = 0; itemGraphColCapacity[i] = 0; } vector groupDegree(n + m, 0); vector itemDegree(n, 0); vector id(n + m); for (int i = 0; i < n + m; i++) { id[i] = i; } int leftId = m; 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]] = new int(*groupItemColCapacity[group[i]]); } groupItem[group[i]]->push_back(i); } for (int i = 0; i < n; i++) { int curGroupId = group[i]; for (int j = 0; j < beforeItems[i].size(); 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] = new int(*itemGraphColCapacity[item]); } itemGraph[item]->push_back(i); } else { groupDegree[curGroupId]++; if (groupGraphColSize[beforeGroupId] == groupGraphColCapacity[beforeGroupId]) { int* x = &groupGraphColCapacity[beforeGroupId]; (*x) = (*x) ? (*x) * 2 : 1; groupGraph[beforeGroupId] = new int(*groupGraphColCapacity[beforeGroupId]); } groupGraph[beforeGroupId]->push_back(curGroupId); } } } queue q; for (int i = 0; i < n; i++) { if (itemDegree[i] == 0) { q.push(i); } } int countItem = 0; vector g_items; while (!q.empty()) { int u = q.front(); q.pop(); countItem++; g_items.push_back(u); for (int v = 0; v < itemGraphColSize[u]; v++) { int item = itemGraph[u][v]; if (--itemDegree[item] == 0) { q.push(item); } } } if (countItem != n) { return vector (); } queue groupQ; for (int i = 0; i < m; i++) { if (groupDegree[i] == 0) { groupQ.push(i); } } int countGroup = 0; vector g_order; while (!groupQ.empty()) { int g = groupQ.front(); groupQ.pop(); countGroup++; g_order.push_back(g); for (int h = 0; h < groupGraphColSize[g]; h++) { int group = groupGraph[g][h]; if (--groupDegree[group] == 0) { groupQ.push(group); } } } if (countGroup != m) { return vector (); } vector ans; int idx = 0; for (int g : g_order) { for (int item : *groupItem[g]) { ans[idx++] = item; } } return ans; }} 以下是Python实现：
import collectionsclass 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].add(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: 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/