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]-=1
            if 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+1
                maxGroupId+=1
            distinctGroupsSet.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]+=1
                if beforeGroupId==groupId:
                    groupItemsAdjList[groupId][beforeId].append(itemId)
                    # print(groupItemsIndegreeList[groupId])
                    groupItemsIndegreeList[groupId][itemId]+=1
            if 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

4.执行结果