我的博客

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:

img

1
2
输入: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:

1
2
3
输入: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 就是每个组负责的所有项目列表。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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],[],[],[]]))

评论无需登录,可以匿名,欢迎评论!