项目管理

难度: Hard

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 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 * 10⁴
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] 不含重复元素

Submission

运行时间: 103 ms

内存: 32.3 MB

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        for i in range(len(group)):
            if group[i] == -1:
                group[i] = m
                m += 1
        item_in = [0] * n
        group_in = [0] * m
        g1 = [[] for _ in range(n)]
        g2 = [[] for _ in range(m)]
        for i,t in enumerate(beforeItems):
            cur = group[i]
            for j in t:
                bef = group[j]
                if bef != cur:
                    g2[bef].append(cur)
                    group_in[cur] += 1
                else:
                    g1[j].append(i)
                    item_in[i] += 1
        def typo_sort(indgree,gra):
            q = [i for i,x in enumerate(indgree) if not x]
            ans = []
            while q:
                t = q.pop()
                ans.append(t)
                for nxt in gra[t]:
                    indgree[nxt] -= 1
                    if indgree[nxt] == 0:
                        q.append(nxt)
            return ans
        
        res1 = typo_sort(group_in,g2)
        res2 = typo_sort(item_in,g1)
        if len(res1) != m or len(res2) != n:
            return []
        grk = [-1] * m
       
        for i,x in enumerate(res1):
            grk[x] = i
    
        res2.sort(key=lambda x:grk[group[x]])
        return res2

Explain

此题解采用两级拓扑排序来解决问题。首先，对于不属于任何小组的项目，将其各自分配到一个新的单独小组中。然后，创建两个图：一个是项目的依赖图（同一小组内的项目间依赖），另一个是小组间的依赖图。对每个项目和小组，我们分别维护一个入度数组，表示每个节点的依赖数。使用拓扑排序首先对小组进行排序，然后对单个项目进行排序。如果在任何一级排序中未能包含所有项目或所有小组，则返回空数组表示无法完成排序。最后，根据小组的排序结果，对项目进行排序并返回最终结果。

时间复杂度: O(m + n + E)

空间复杂度: O(m + n + E)

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        # 对不属于任何小组的项目分配独立小组
        for i in range(len(group)):
            if group[i] == -1:
                group[i] = m
                m += 1
        # 初始化项目和小组的入度以及依赖图
        item_in = [0] * n
        group_in = [0] * m
        g1 = [[] for _ in range(n)]
        g2 = [[] for _ in range(m)]
        # 建立依赖关系
        for i, t in enumerate(beforeItems):
            cur = group[i]
            for j in t:
                bef = group[j]
                if bef != cur:
                    g2[bef].append(cur)
                    group_in[cur] += 1
                else:
                    g1[j].append(i)
                    item_in[i] += 1
        # 拓扑排序函数
        def typo_sort(indgree, gra):
            q = [i for i, x in enumerate(indgree) if not x]
            ans = []
            while q:
                t = q.pop()
                ans.append(t)
                for nxt in gra[t]:
                    indgree[nxt] -= 1
                    if indgree[nxt] == 0:
                        q.append(nxt)
            return ans
        # 对小组和项目进行拓扑排序
        res1 = typo_sort(group_in, g2)
        res2 = typo_sort(item_in, g1)
        # 检查是否所有的项目和小组都被排序了
        if len(res1) != m or len(res2) != n:
            return []
        # 小组排序结果映射
        grk = [-1] * m
        for i, x in enumerate(res1):
            grk[x] = i
        # 根据小组的排序结果对项目进行最终排序
        res2.sort(key=lambda x: grk[group[x]])
        return res2

Explore

在初始化入度数组时，我们遍历每个项目的依赖项列表。对于每个项目，我们检查其依赖的项目是否属于同一小组。如果属于同一小组，则项目的入度增加；如果属于不同的小组，则该项目所在小组的入度增加。这样确保了每个项目和小组的入度准确反映了其所有的外部依赖关系。

将不属于任何小组的项目分配到新的独立小组确实会增加小组的总数量，从而可能增加小组间依赖的复杂度。每个独立项目形成一个单独的小组，可能导致更多的小组间依赖关系，尤其是当这些独立项目与其他小组或项目有依赖关系时。然而，这种方法是必要的，因为它允许我们在拓扑排序中有效地处理那些没有明确归属的项目。

题解中并没有直接确保依赖图中不存在循环依赖，这通常是依赖于输入数据的约束。拓扑排序的基本前提是依赖图必须是有向无环图（DAG）。如果存在循环依赖，即图中存在环，拓扑排序过程中将无法完成所有节点的排序。在这种情况下，排序过程中未能被完全处理的节点数量将不等于总节点数，最终返回的结果将是空数组，表示无法进行有效的排序。

在拓扑排序中使用队列而不是栈，是因为队列实现了广度优先搜索（BFS），这有助于按逻辑顺序（即从无依赖到有依赖的顺序）处理节点。使用队列可以保证每次处理的都是当前没有任何未解决依赖的节点。如果使用栈（实现深度优先搜索DFS），虽然同样能实现拓扑排序，但生成的顺序可能会不同，这在某些情况下可能会影响到结果的使用或理解，尤其是在有多种有效拓扑排序的情况下。使用队列通常可以提供更直观和一致的排序结果。