Leetcode 1203. 项目管理

1.题目基本信息

1.1.题目描述

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。
项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个空列表。

1.2.题目地址

https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/description/

2.解题方法

2.1.解题思路

拓扑排序

2.2.解题步骤

第一步，-1的组的重新定义

第二步，构建组间邻接表和组内邻接表

第三步，组间拓扑排序

第四步，组内拓扑排序

3.解题代码

Python代码

from typing import Dict,List
from collections import deque,defaultdict
# ==> 通过Dict[List]结构的邻接表图和Dict形式的入度信息进行拓扑排序，返回拓扑排序序列，如果不存在，则返回空列表
def topoSort(adjListGraph:Dict[object,List[object]],inDegreeList:Dict[object,int]):que=deque()for node in adjListGraph.keys():inDegree=inDegreeList[node]if inDegree==0:que.append(node)result=[]while que:node=que.popleft()result.append(node)for subNode in adjListGraph[node]:inDegreeList[subNode]-=1if inDegreeList[subNode]==0:que.append(subNode)return result if len(result)==len(adjListGraph) else []class Solution:def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:# 第一步，-1的组的重新定义maxGroupId=max(group)distinctGroupsSet=set()for i in range(len(group)):if group[i]==-1:group[i]=maxGroupId+1maxGroupId+=1distinctGroupsSet.add(group[i])distinctGroups=list(distinctGroupsSet)# 第二步，构建组间邻接表和组内邻接表groupsAdjList=defaultdict(list) # 组间的邻接表groupsIndegreeList=defaultdict(int) # 组间邻接表的入度表groupItemsAdjList={groupId:defaultdict(list) for groupId in distinctGroups}  # 各个组中各个元素的邻接表groupItemsIndegreeList={groupId:defaultdict(int) for groupId in distinctGroups}  # 各个组中各个元素的邻接表的入度信息for groupId in distinctGroups:groupsAdjList[groupId]=[]for i in range(n):itemId,groupId,beforeIds=i,group[i],beforeItems[i]for beforeId in beforeIds:beforeGroupId=group[beforeId]if beforeGroupId!=groupId and groupId not in groupsAdjList[beforeGroupId]:groupsAdjList[beforeGroupId].append(groupId)groupsIndegreeList[groupId]+=1if beforeGroupId==groupId:groupItemsAdjList[groupId][beforeId].append(itemId)# print(groupItemsIndegreeList[groupId])groupItemsIndegreeList[groupId][itemId]+=1if itemId not in groupItemsAdjList[groupId]:groupItemsAdjList[groupId][itemId]=[]# 第三步，组间拓扑排序groupSortArr=topoSort(groupsAdjList,groupsIndegreeList)if not groupSortArr:return []# print(groupSortArr)# 第四步，组内拓扑排序result=[]for groupId in groupSortArr:thisItemsArr=topoSort(groupItemsAdjList[groupId],groupItemsIndegreeList[groupId])# print(groupId,thisItemsArr,groupItemsAdjList[groupId])if not thisItemsArr:return []result.extend(thisItemsArr)# print(result)return result