leetcode weekly 155 5200. 项目管理 1203. Sort Items by Groups Respecting Dependencies

目录

1. 解答

公司共有 n 个项目和 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*10^4
• 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]

解答

我没想出这个题的做法。看到比赛中国榜单第 8 名的 hansirchen 的做法。

具体是把小组之间的依赖和小组内的依赖分开处理。而且处理的方法是一模一样的。

定义 gf、gs、pf、ps四个 set 字典，分别存储小组的和项目的依赖。f 代表他的父亲（就是所依赖的），s 代表儿子（依赖他的）。g 代表组，p 代表项目。

gp 就是每个组负责的所有项目列表。

另外，需要为所有没有组的项目创建一个新的组。

对于每一个依赖的处理是这样的，定义一个空的列表，放当前可以满足的。初始就是那些没有任何依赖的组或者项目。

然后从头遍历这个列表，每遍历一个，就把这个组或者项目的儿子节点检查一遍，删掉他们的关系，如果这是这个儿子节点的依赖删干净了，就把这个儿子加入到可满足列表中。

from collections import defaultdict
class Solution:
    def sortItems(self, n: int, m: int, group, beforeItems):
        gf = defaultdict(set) # gf[gid] gid 依赖的所有小组
        gs = defaultdict(set) # gs[gid]所有依赖 gid 组的小组
        pf = defaultdict(set) # pf[pid] pid 依赖的所有项目
        ps = defaultdict(set) # ps[pid] 所有依赖 pid 的项目
        gp = defaultdict(list) # gp[gid] 是 gid 组负责的所有项目
        ngid = -1
        for i in range(n):
            if group[i] == -1: # 为没有组的项目创建一个新的组
                group[i] = ngid
                ngid -= 1
            gp[group[i]].append(i)
        
        for i, (gid, dep_p) in enumerate(zip(group, beforeItems)):
            dep = [[pid, group[pid]] for pid in dep_p]
            for pid, dgid in dep:
                if gid != dgid:
                    gf[gid].add(dgid)
                    gs[dgid].add(gid)
                else:
                    pf[i].add(pid)
                    ps[pid].add(i)
        
        avl_g = [] # 当前可满足的小组
        for gid in set(group):
            if gid not in gf: # 所有没有依赖的小组都可满足
                avl_g.append(gid)
        
        i = 0
        while i < len(avl_g):
            gid = avl_g[i]
            if gid in gs:
                for son in gs[gid]:
                    gf[son].remove(gid)
                    if len(gf[son]) == 0:
                        avl_g.append(son)
            i += 1

        if len(avl_g) != len(set(group)): # 存在组无法满足
            return []
        result = []
        for gid in avl_g:
            p_list = gp[gid]
            avl_p = [] # 当前可满足的项目
            for p in p_list:
                if p not in pf: # 所有没有依赖的项目都可满足
                    avl_p.append(p)
            i = 0
            while i < len(avl_p):
                pid = avl_p[i]
                if pid in ps:
                    for son in ps[pid]:
                        pf[son].remove(pid)
                        if len(pf[son]) == 0:
                            avl_p.append(son)
                i += 1
            if len(avl_p) != len(p_list): return [] # 存在无法满足的项目
            result.extend(avl_p)
        return result
s = Solution()
print(s.sortItems(n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]))