【Day 31 】2023-12-16 - 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] 不含重复元素

[laurallalala]

class Solution:
    def has_cycle(self, graph, cur_node, visited, result):
        if visited[cur_node] == 1:
            return False
        if visited[cur_node] == 2:
            return True
        visited[cur_node] = 2
        for next_node in graph[cur_node]:
            if self.has_cycle(graph, next_node, visited, result):
                return True
        visited[cur_node] = 1
        result.append(cur_node)
        return False

    def sortItems(self, n: int, m: int, group: List[int],
                  beforeItems: List[List[int]]) -> List[int]:
        # Map between group_id and item_ids
        group_items_map = defaultdict(list)
        # Visited for items in each group. Will be used later
        visited_item = defaultdict(dict)
        for i in range(n):
            # Assign no-group items to a new group
            if group[i] == -1:
                group[i] = m
                m += 1
            group_items_map[group[i]].append(i)
            visited_item[group[i]][i] = 0

        # key - group_id : value - next_groups
        graph_group = defaultdict(set)
        # key - group_id : value - {key - item_id : value: next_items}
        graph_item = {i: defaultdict(list) for i in range(m)}

        # Create graph for items and groups
        for item_after, before_items in enumerate(beforeItems):
            for item_before in before_items:
                group_before = group[item_before]
                group_after = group[item_after]

                # If two items belong to different groups,
                #   add a dependency between groups
                # Otherwise, add a dependency between items in the same group
                if group_before != group_after:
                    graph_group[group_before].add(group_after)
                else:
                    graph_item[group_before][item_before].append(item_after)

        # Use DFS to find group order
        visited_group = [0] * m
        group_order = []
        for group_id in range(m):
            if self.has_cycle(graph_group, group_id,
                              visited_group, group_order):
                return []

        # Use DFS to find item order in each group
        full_item_order = []
        for group_id in group_order:
            for item_id in group_items_map[group_id]:
                if self.has_cycle(graph_item[group_id], item_id,
                                  visited_item[group_id], full_item_order):
                    return []
        return full_item_order[::-1]

[snmyj]

class Solution {
public:
    vector<int> topSort(vector<int>& deg, vector<vector<int>>& graph, vector<int>& items) {
        queue<int> Q;
        for (auto& item: items) {
            if (deg[item] == 0) {
                Q.push(item);
            }
        }
        vector<int> res;
        while (!Q.empty()) {
            int u = Q.front(); 
            Q.pop();
            res.emplace_back(u);
            for (auto& v: graph[u]) {
                if (--deg[v] == 0) {
                    Q.push(v);
                }
            }
        }
        return res.size() == items.size() ? res : vector<int>{};
    }

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);

        // 组间和组内依赖图
        vector<vector<int>> groupGraph(n + m);
        vector<vector<int>> itemGraph(n);

        // 组间和组内入度数组
        vector<int> groupDegree(n + m, 0);
        vector<int> itemDegree(n, 0);

        vector<int> id;
        for (int i = 0; i < n + m; ++i) {
            id.emplace_back(i);
        }

        int leftId = m;
        // 给未分配的 item 分配一个 groupId
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem[group[i]].emplace_back(i);
        }
        // 依赖关系建图
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item: beforeItems[i]) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph[item].emplace_back(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].emplace_back(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return vector<int>{};
        } 
        vector<int> ans;
        // 组内拓扑关系排序
        for (auto& curGroupId: groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) {
                continue;
            }
            vector<int> res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (res.size() == 0) {
                return vector<int>{};
            }
            for (auto& item: res) {
                ans.emplace_back(item);
            }
        }
        return ans;
    }
};

[Chloe-C11]

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        groupId = m
        for i in range(n):
            if group[i] == -1:
                group[i] = groupId
                groupId += 1

        itemGraph = defaultdict(list)
        itemIndegree = [0] * n
        groupGraph = defaultdict(list)  # Initialize groupGraph
        groupIndegree = [0] * groupId

        for i in range(n):
            for prev in beforeItems[i]:
                itemGraph[prev].append(i)
                itemIndegree[i] += 1
                if group[i] != group[prev]:
                    groupGraph[group[prev]].append(group[i])
                    groupIndegree[group[i]] += 1

        itemOrder = self.topologicalSort(itemGraph, itemIndegree)
        groupOrder = self.topologicalSort(groupGraph, groupIndegree)

        if not itemOrder or not groupOrder:
            return []

        orderedGroups = defaultdict(list)
        for item in itemOrder:
            orderedGroups[group[item]].append(item)

        answerList = []
        for groupIndex in groupOrder:
            answerList.extend(orderedGroups[groupIndex])

        return answerList

    def topologicalSort(self, graph: Dict[int, List[int]], indegree: List[int]) -> List[int]:
        visited = []
        stk = []
        for i in range(len(indegree)):
            if indegree[i] == 0:
                stk.append(i)

        while stk:
            curr = stk.pop()
            visited.append(curr)

            for n in graph[curr]:
                indegree[n] -= 1
                if indegree[n] == 0:
                    stk.append(n)

        return visited if len(visited) == len(graph) else []

[Danielyan86]

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

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    deque.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = 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 pres[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_sort([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_sort(group_projects[group_id], project_indegree, project_neighbors)

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

        return ans

[larscheng]

思路

本题个人感觉难度较大，参考了题解先打个卡，知识点：建图、入度出度、拓扑排序 参考题解： 【图解】拓扑排序（1203. 项目管理）、1203. 项目管理-视频讲解

代码

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：实例化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

[adfvcdxv]

什么dick题目，读了半天都没读懂题目

class Solution { public: using UMIV = unordered_map<int, vector >; using UMII = unordered_map<int, int>; using VVI = vector<vector >; using VI = vector; UMIV sub; vector sortItems(int n, int m, vector& group, vector<vector>& befores) { for (int j = 0; j < n; j++) { if (group[j] == -1) group[j] = m++; }

    vector<vector<int> > gg(m);
    for (int j = 0; j < n; j++) gg[group[j]].push_back(j);

    for (int i = 0; i < gg.size(); i++) {
        // 对于组内只有一个任务的小组，直接加入sub结果集，不走topo
        if (gg[i].size() == 1) {
            int itemId = gg[i][0];
            sub[group[itemId]]= {itemId};
            continue;
        }
        bool f = topoSort(i, gg[i], befores);
        if (f == false) return {};
    }

    VI groups; 
    for (int i = 0; i < m; i++) groups.push_back(i);
    VVI newbefore(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < befores[i].size(); j++) {
            int prevId = group[befores[i][j]];
            if (prevId != group[i]) newbefore[group[i]].push_back(prevId);
        }
    }
    if(!topoSort(m, groups, newbefore)) return {};
    VI rs;
    for (auto v : sub[m]) rs.insert(rs.end(), sub[v].begin(), sub[v].end());
    return rs;
}

bool topoSort(int gpid, VI& num, VVI& bef) {
    int n = num.size();
    UMII degree; 
    UMIV g; 
    for (int i = 0; i < n; i++) {
        degree[num[i]] = 0;
        g[num[i]] = vector<int>();
    }
    for (int i = 0; i < n; i++) {
        int idx = num[i];
        if(bef[idx].size() == 0) continue;
        for (int j = 0; j < bef[idx].size(); j++) {
            int last = bef[idx][j];
            if (degree.find(last) == degree.end()) continue;
            g[last].push_back(idx);
            degree[idx]++;
        }
    }
    VI res;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (degree[num[i]] == 0) 
            q.push(num[i]);
    }
    while (!q.empty()) {
        int cur = q.front();
        res.push_back(cur);
        if (g[cur].size() != 0) {
            for (int i = 0; i < g[cur].size(); i++) {
                if (--degree[g[cur][i]] == 0) q.push(g[cur][i]);
            }
        }
        q.pop();
    }
    sub[gpid] = move(res);
    return sub[gpid].size() == n;
}

};