LeetCode：1203. Sort Items by Groups Respecting Dependencies项目管理（C语言）

太过爱你忘了你带给我的痛 2023-01-05 12:07 13阅读 0赞

**题目描述：**  
公司共有 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\]

示例 2：

输入：n = 8, m = 2, group = \[-1,-1,1,0,0,1,0,-1\], beforeItems = \[\[\],\[6\],\[5\],\[6\],\[3\],\[\],\[4\],\[\]\]  
输出：\[\]  
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

提示：

1 <= m <= n <= 3 * 104
    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] 不含重复元素

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

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;
    }
    
    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;
    }

**运行结果：**  
![在这里插入图片描述][20210112091001609.png_pic_center]

**Notes：**  
参考官方文档：[https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/solution/xiang-mu-guan-li-by-leetcode-solution-3e7j/][https_leetcode-cn.com_problems_sort-items-by-groups-respecting-dependencies_solution_xiang-mu-guan-li-by-leetcode-solution-3e7j]

[20210112091001609.png_pic_center]: /images/20221119/bd5a3f3f12a84c7795f7e1517754ee65.png
[https_leetcode-cn.com_problems_sort-items-by-groups-respecting-dependencies_solution_xiang-mu-guan-li-by-leetcode-solution-3e7j]: https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/solution/xiang-mu-guan-li-by-leetcode-solution-3e7j/