【Day 31 】2024-05-08 - 1203. 项目管理

[azl397985856]

1203. 项目管理

入选理由

暂无

题目地址

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

前置知识

• 图论
• 拓扑排序
• BFS & DFS

  题目描述

公司共有 n 个项目和  m 个小组，每个项目要不无人接手，要不就由 m 个小组之一负责。

group[i] 表示第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）小组可能存在没有接手任何项目的情况。

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

同一小组的项目，排序后在列表中彼此相邻。 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。 如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

 

示例 1：

![](https://p.ipic.vip/nrmqt5.jpg)

输入：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 * 104 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] 不含重复元素

[zhiyuanpeng]

class Solution: def sortItems(self, n, m, group, beforeItems):

If an item belongs to zero group, assign it a unique group id.

    group_id = m
    for i in range(n):
        if group[i] == -1:
            group[i] = group_id
            group_id += 1

    # Sort all item regardless of group dependencies.
    item_graph = [[] for _ in range(n)]
    item_indegree = [0] * n

    # Sort all groups regardless of item dependencies.
    group_graph = [[] for _ in range(group_id)]
    group_indegree = [0] * group_id      

    for curr in range(n):
        for prev in beforeItems[curr]:
            # Each (prev -> curr) represents an edge in the item graph.
            item_graph[prev].append(curr)
            item_indegree[curr] += 1

            # If they belong to different groups, add an edge in the group graph.
            if group[curr] != group[prev]:
                group_graph[group[prev]].append(group[curr])
                group_indegree[group[curr]] += 1      

    # Tologlogical sort nodes in graph, return [] if a cycle exists.
    def topologicalSort(graph, indegree):
        visited = []
        stack = [node for node in range(len(graph)) if indegree[node] == 0]
        while stack:
            cur = stack.pop()
            visited.append(cur)
            for neib in graph[cur]:
                indegree[neib] -= 1
                if indegree[neib] == 0:
                    stack.append(neib)
        return visited if len(visited) == len(graph) else []

    item_order = topologicalSort(item_graph, item_indegree)
    group_order = topologicalSort(group_graph, group_indegree)

    if not item_order or not group_order: 
        return []

    # Items are sorted regardless of groups, we need to 
    # differentiate them by the groups they belong to.
    ordered_groups = collections.defaultdict(list)
    for item in item_order:
        ordered_groups[group[item]].append(item)

    # Concatenate sorted items in all sorted groups.
    # [group 1, group 2, ... ] -> [(item 1, item 2, ...), (item 1, item 2, ...), ...]
    answer = []
    for group_index in group_order:
        answer += ordered_groups[group_index]
    return answer

[yashuning]

思路：主体：拓扑排序

代码：

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        # 子方法，当某一个组对外无依赖之后，拓扑排序组内元素，并且按顺序输出
        def tp_sort(gids,inner_p_map):
            res = []
            igs = {}
            for g in gids:
                igs[g]=0
            for g in gids:
                if g in inner_p_map:
                    cs = inner_p_map[g]
                    for ccs in cs:
                        igs[ccs] += 1
            while len(res) != len(gids):
                cur = []
                for g in  gids:
                    if g in igs and  igs[g]==0:
                        cur.append(g)
                        del(igs[g])
                        if g in inner_p_map:
                            cs = inner_p_map[g]
                            for ccs in cs:
                                igs[ccs]-=1
                if len(res) != len(gids) and not cur:return []
                res.extend(cur)

            return res

        res = []
        groups = set()
        inf = -100000
        group_input_degree = {} # key 为组号，val为入度，-1组的组号为-1*项目号，当0号项目的组为-1时，取-100000表示，取巧操作
        group_mem_id = {} # key为组号，val为组员项目id的list
        p_map = {} # 每个项目对应的组的下游，组间依赖
        inner_p_map = {} # 每个项目对应的组内下游，组内依赖
        for i,x in enumerate(group):
            if x == -1:
                bis = beforeItems[i]
                gid = -1 * i if i !=0 else inf
                group_input_degree[gid] = len(bis)
                for bi in bis:
                    if bi not in p_map:
                        p_map[bi] = set()
                    p_map[bi].add(gid)
            else:
                gid = x 
                if gid not in group_mem_id:
                    group_mem_id[gid] = set()
                group_mem_id[gid].add(i)
            groups.add(gid)
        for gid in group_mem_id:
            if gid < 0 :continue
            gms = group_mem_id[gid]
            for g in gms:
                par = beforeItems[g]
                if par:
                    for p in par:
                        if p in gms:
                            if p not in inner_p_map:
                                inner_p_map[p]=set()
                            inner_p_map[p].add(g)
                        else:
                            if p not in p_map:
                                p_map[p]=set()
                            p_map[p].add(gid)
        # 初始化每个组的入度
        for g in groups:
            group_input_degree[g]=0
        for p,gg in p_map.items():
            for g in gg:
                group_input_degree[g] += 1
        while group_input_degree:
            cur = []
            used = set()
            for g in group_input_degree:
                if group_input_degree[g]==0:
                    if g < 0:
                        it = -1 * g if g != inf else 0
                        res.append(it)
                        if it in p_map:
                            cur.extend(list(p_map[it]))
                    else:
                        gids = group_mem_id[g]
                        tmp = tp_sort(gids,inner_p_map)
                        if not tmp:return []
                        res.extend(tmp)
                        for it in group_mem_id[g]:
                            if it in p_map:
                                cur.extend(list(p_map[it]))
                    used.add(g)
            for u in used:
                del(group_input_degree[u])
            if group_input_degree and not cur:return []
            for cc in cur:
                group_input_degree[cc]-=1
        return res

[xil324]

class Solution(object):
    def sortItems(self, n, m, group, beforeItems):
        """
        :type n: int
        :type m: int
        :type group: List[int]
        :type beforeItems: List[List[int]]
        :rtype: List[int]
        """
        index = m
        group_items_map = [[] for _ in range(n + m)]
        for item, groupItem in enumerate(group):
            if groupItem == -1:
                group[item] = index
                index+=1
            group_items_map[group[item]].append(item)

        items_degree= [0] * n
        groups_degree = [0] * (n+m)
        items_graph = [[] for _ in range(n)]
        groups_graph = [[] for _ in range(n+m)]

        for i, groupNumber in enumerate(group):
            for j in beforeItems[i]:
                if group[j] == groupNumber:
                    items_degree[i] += 1
                    items_graph[j].append(i)
                else:
                    groups_degree[groupNumber] += 1
                    groups_graph[group[j]].append(groupNumber)

        group_order = self.sort(groups_degree, groups_graph, list(range(n+m)))
        if not group_order:
            return []

        res = []
        for group_index in group_order:
            item_order = self.sort(items_degree,items_graph,group_items_map[group_index] )
            if len(item_order) != len(group_items_map[group_index]):
                return []
            res.extend(item_order)
        return res

    def sort(self, degrees, graph, items):
            queue = deque([item for item in items if degrees[item] == 0])
            result = []
            while queue:
                current = queue.popleft()
                result.append(current)
                for neighbor in graph[current]:
                    degrees[neighbor] -= 1
                    if degrees[neighbor] == 0:
                        queue.append(neighbor)
            return result if len(result) == len(items) else []

[CathyShang]

class Solution:
    def tp_sorted(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)
        return ans
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        max_group_id = m 
        for i in range(n):
            if group[i] == -1:
                group[i] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)
            for pre in beforeItems[project]:
                if group[pre] != group[project]:
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)
        ans = []
        group_queue = self.tp_sorted([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if(len(group_queue)!=max_group_id):
            return []
        for group_id in group_queue:
            project_queue = self.tp_sorted(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

[Hermione666]

class Solution: def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

Dependency counters for items and groups

    item_deps_count = [0] * n
    group_deps_count = [0] * m

    # Queue for items without groups and queues for each group
    no_group_items = []
    group_items = [[] for _ in range(m)]
    ready_groups = []

    # Adjacency list for tracking which items depend on a given item
    dependents = [[] for _ in range(n)]

    # Build dependency graph and initialize queues
    for item, dependencies in enumerate(beforeItems):
        item_deps_count[item] = len(dependencies)
        item_group = group[item]
        for dep_item in dependencies:
            dependents[dep_item].append(item)
            if item_group != -1 and group[dep_item] != item_group:
                group_deps_count[item_group] += 1
        if not dependencies:
            (group_items[item_group] if item_group != -1 else no_group_items).append(item)

    # Initialize the queue of ready groups
    for i, deps in enumerate(group_deps_count):
        if deps == 0:
            ready_groups.append(group_items[i])

    result = []
    while ready_groups or no_group_items:
        current_queue = ready_groups.pop() if ready_groups else no_group_items

        while current_queue:
            item = current_queue.pop()
            result.append(item)
            item_group = group[item]

            # Process all items depending on the current item
            for dependent in dependents[item]:
                dependent_group = group[dependent]
                item_deps_count[dependent] -= 1
                if not item_deps_count[dependent]:
                    (group_items[dependent_group] if dependent_group != -1 else no_group_items).append(dependent)

                # If dependent is in a different group, manage group dependencies
                if dependent_group != -1 and dependent_group != item_group:
                    group_deps_count[dependent_group] -= 1
                    if group_deps_count[dependent_group] == 0:
                        ready_groups.append(group_items[dependent_group])

    return result if len(result) == n else []

[Dtjk]

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {

        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        List<Integer>[] groupGraph = new ArrayList[m];
        List<Integer>[] itemGraph = new ArrayList[n];
        for (int i = 0; i < m; i++) groupGraph[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) itemGraph[i] = new ArrayList<>();

        int[] groupIndegree = new int[m];
        int[] itemIndegree = new int[n];

        int len = group.length; // m changed
        for (int i = 0; i < len; i++) {
            int curGroup = group[i];
            for (int beforeItem: beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != curGroup) {
                    groupGraph[beforeGroup].add(curGroup);
                    groupIndegree[curGroup]++;
                }
            }
        } 
}