【Day 31 】2022-05-01 - 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://tva1.sinaimg.cn/large/008eGmZEly1gmkv6dy054j305b051mx9.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] 不含重复元素

[xingchen77]

不会，先抄下打卡

class Solution:
    def tp_sort(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 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 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_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

[houmk1212]

思路

参考了leecode题解，知道要用拓扑排序，但是没想到使用双重拓扑排序

代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

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<>();
    }
}

[antmUp]

代码

class Solution:
    def tp_sort(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], 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

时间复杂度：o(n+m) 空间复杂度：o(n+m)

[xiayuhui231]

代码

class Solution {
public:
    vector<int> topologicalSort(vector<vector<int>> &Adj, vector<int> &Indegree, int n){
        vector<int> res;
        queue<int> q;
        for(int i = 0;i<n;i++){
            if(Indegree[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int front = q.front();
            q.pop();
            res.push_back(front);
            for(int successor: Adj[front]){
                Indegree[successor]--;
                if(Indegree[successor]==0){
                    q.push(successor);
                }
            }
        }
        if(res.size()==n){return res;}
        return vector<int>();
    }
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for(int i=0;i<group.size();i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }
        // 第 2 步：实例化组和项目的邻接表
        vector<vector<int>> groupAdj(m, vector<int>());
        vector<vector<int>> itemAdj(n, vector<int>());

        // 第 3 步：建图和统计入度数组
        vector<int> groupsIndegree(m, 0);
        vector<int> itemIndegree(n, 0);

        int len = group.size();
        for(int i=0;i<len;i++){
            int currentGroup = group[i];
            for(int beforeItem: beforeItems[i]){
                int beforeGroup = group[beforeItem];
                if(beforeGroup!=currentGroup){
                    groupAdj[beforeGroup].push_back(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int item: beforeItems[i]){
                itemAdj[item].push_back(i);
                itemIndegree[i]++;
            }
        }
        // 第 4 步：得到组和项目的拓扑排序结果
        vector<int> groupList = topologicalSort(groupAdj, groupsIndegree, m);
        if(groupList.size()==0){
            return vector<int> ();
        }
        vector<int> itemList = topologicalSort(itemAdj, itemIndegree, n);
        if(itemList.size()==0){
            return vector<int> ();
        }
        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        map<int, vector<int>> group2Items;
        for(int item: itemList){
            group2Items[group[item]].push_back(item);
        }
        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        vector<int> res;
        for(int groupId: groupList){
            vector<int> items = group2Items[groupId];
            for(int item: items){
                res.push_back(item);
            }
        }
        return res;
    } 
};

[currybeefer]

先打卡，之后慢慢看吧 class Solution: def tp_sort(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], 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

[MichaelXi3]

Idea

• Topological sort

  Code

  class Solution {
  Map <Integer, List<Integer>> groupGraph;
  Map <Integer, List<Integer>> itemGraph;
  
  int[] groupsIndegree;
  int[] itemsIndegree;
  
  private void buildGraphOfGroups(int[] group, List<List<Integer>> beforeItems, int n) {
  for (int i=0;i<group.length;i++) {
    int toGroup = group[i];
    List <Integer> fromItems = beforeItems.get(i);
    for (int fromItem : fromItems) {
      int fromGroup = group[fromItem];
      if(fromGroup != toGroup) {
        groupGraph.computeIfAbsent(fromGroup, x->new ArrayList()).add(toGroup); 
        groupsIndegree[toGroup]++;
      }        
    }
  }
  }
  
  private void buildGraphOfItems(List<List<Integer>> beforeItems, int n) {
  for (int i=0;i<n;i++) {
    List<Integer> items = beforeItems.get(i);
    for (Integer item : items) {
      itemGraph.computeIfAbsent(item, x->new ArrayList()).add(i);
      itemsIndegree[i]++;
    }
  }
  }
  
  private List<Integer> topologicalSortUtil(Map <Integer, List<Integer>> graph, int[] indegree, int n) {
  List <Integer> list = new ArrayList<Integer>();
  Queue <Integer> queue = new LinkedList();
  for (int key : graph.keySet()) {
    if(indegree[key] == 0) {
      queue.add(key);
    }
  }
  
  while(!queue.isEmpty()) {
    int node = queue.poll();
    n--;
    list.add(node);
    for (int neighbor : graph.get(node)) {
      indegree[neighbor] --;        
      if(indegree[neighbor] == 0) {
        queue.offer(neighbor);          
      }
    }
  }    
  return n == 0 ? list : new ArrayList();
  }  
  
  public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
  groupGraph = new HashMap();
  itemGraph = new HashMap();
  
  // Each item belongs to a group. If an item doesn't have a group it forms it's own isolated group.
  for (int i=0;i<group.length;i++) {
    if(group[i] == -1) group[i] = m++;
  }  
  
  for (int i=0;i<m;i++) {
    groupGraph.put(i, new ArrayList());      
  }
  
  for (int i=0;i<n;i++) {
    itemGraph.put(i, new ArrayList());      
  }
  
  groupsIndegree = new int[m];
  itemsIndegree = new int[n];    
  
  // form graph structure across different groups and also calculate indegree.
  buildGraphOfGroups(group, beforeItems, n);
  
  // form graph structure across different items and also calculate indegree.
  buildGraphOfItems(beforeItems, n);
  
  // Topological ordering of the groups.
  List<Integer> groupsList = topologicalSortUtil(groupGraph, groupsIndegree, m);
  // Topological ordering of the items.
  List<Integer> itemsList = topologicalSortUtil(itemGraph, itemsIndegree, n);
  
  // Detect if there are any cycles.
  if(groupsList.size() == 0 || itemsList.size() == 0) return new int[0];    
  
  // This Map holds relative order of items in the same group computed in the loop below. 
  Map <Integer, List<Integer>> groupsToItems = new HashMap();
  
  for (Integer item : itemsList) {
    groupsToItems.computeIfAbsent(group[item], x->new ArrayList()).add(item);
  }
  
  int[] ans = new int[n];
  int idx = 0;
  for (Integer grp : groupsList) {
    List <Integer> items = groupsToItems.getOrDefault(grp, new ArrayList());
    for (Integer item : items) {
      ans[idx++] = item;  
    }      
  }
  
  return ans;
  }
  }

[lxgang65]

暂时完全不会

import java.util.ArrayList;
import java.util.List;

public class Solution  {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<Integer> res = new ArrayList<>();
        List<Integer>[] graph = new ArrayList[n + m];
        int[] indegree = new int[n + m];

        for (int i = 0; i < n + m; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                continue;
            }
            graph[n + group[i]].add(i);
            indegree[i]++;
        }

        for (int i = 0; i < beforeItems.size(); i++) {
            for (int item : beforeItems.get(i)) {
                int repBeforeItem = group[item] == -1 ? item : n + group[item];
                int repCurrentItem = group[i] == -1 ? i : n + group[i];

                if (repBeforeItem == repCurrentItem) {
                    graph[item].add(i);
                    indegree[i]++;
                }
                else {
                    graph[repBeforeItem].add(repCurrentItem);
                    indegree[repCurrentItem]++;
                }
            }
        }

        for (int i = 0; i < n + m; i++) {
            if (indegree[i] == 0) {
                dfs(graph, indegree, i, n, res);
            }
        }

        return (res.size() == n) ? res.stream().mapToInt(i -> i).toArray() : new int[]{};
    }

    private void dfs(List<Integer>[] graph, int[] indegree, int cur, int n, List<Integer> res) {
        if (cur < n) {
            res.add(cur);
        }
        indegree[cur]--;

        for (int child : graph[cur]) {
            if (--indegree[child] == 0) {
                dfs(graph, indegree, child, n, res);
            }
        }
    }
}

[YuyingLiu2021]

class Solution:
    def sortItems(self, n, m, group, beforeItems):
        from collections import defaultdict
        group_inter = [0] * n
        topo1 = []
        for i in range(n):
            if group[i] == -1:
                group_inter[i] = m
                m += 1
            else:
                group_inter[i] = group[i]
        before = [set() for _ in range(m)]
        for (i, item) in enumerate(beforeItems):
            for a in item:
                if group_inter[a] != group_inter[i]:
                    before[group_inter[i]].add(group_inter[a])
        # 组间
        vis = [0] * m
        def topo1_sort(x):
            vis[x] = 1
            for a in before[x]:
                if vis[a] == 0 and not topo1_sort(a):
                    return False
                elif vis[a] == 1:
                    return False
            vis[x] = 2
            topo1.append(x)
            return True

        for i in range(m):
            if vis[i] == 0:
                if not topo1_sort(i):
                    # print(1)
                    return []

        ret = [[] for _ in range(m)]

        #组内
        topo2 = []
        vis = [0] * n
        def topo2_sort(x):
            vis[x] = 1
            for a in beforeItems[x]:
                if vis[a] == 0 and not topo2_sort(a):
                    return False
                elif vis[a] == 1:
                    return False
            vis[x] = 2
            topo2.append(x)
            return True
        for i in range(n):
            if vis[i] == 0:
                if not topo2_sort(i):
                    return []
        for x in topo2:
            ret[group_inter[x]].append(x)        
        ans = []
        for x in topo1:
            ans.extend(ret[x])
        return ans

[PFyyh]

思路

只能看看，学习打卡。

代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

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<>();
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/solution/1203-xiang-mu-guan-li-by-leetcode-t63b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[Ellie-Wu05]

Topo Sort

研究了一晚上，脑子还是晕的，去做了课程表I和课程表II,仿佛有点感觉了，继续研究吧

‘’‘

class Solution: def tpsort(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], 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.tpsort([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.tpsort(group_projects[group_id], project_indegree, project_neighbors)

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

    return ans

’‘’

[zhulin1110]

题目地址(1203. 项目管理)

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

题目描述

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

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

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

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

 

示例 1：

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

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
const topSort = (deg, graph, items) => {
    const Q = [];
    for (const item of items) {
        if (deg[item] === 0) {
            Q.push(item);
        }
    }
    const res = [];
    while (Q.length) {
        const u = Q.shift(); 
        res.push(u);
        for (let i = 0; i < graph[u].length; ++i) {
            const v = graph[u][i];
            if (--deg[v] === 0) {
                Q.push(v);
            }
        }
    }
    return res.length == items.length ? res : [];
}

var sortItems = function(n, m, group, beforeItems) {
    const groupItem = new Array(n + m).fill(0).map(() => []);

    // 组间和组内依赖图
    const groupGraph = new Array(n + m).fill(0).map(() => []);
    const itemGraph = new Array(n).fill(0).map(() => []);

    // 组间和组内入度数组
    const groupDegree = new Array(n + m).fill(0);
    const itemDegree = new Array(n).fill(0);

    const id = new Array(n + m).fill(0).map((v, index) => index);

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

    // 组间拓扑关系排序
    const groupTopSort = topSort(groupDegree, groupGraph, id); 
    if (groupTopSort.length == 0) {
        return [];
    } 
    const ans = [];
    // 组内拓扑关系排序
    for (const curGroupId of groupTopSort) {
        const size = groupItem[curGroupId].length;
        if (size == 0) {
            continue;
        }
        const res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
        if (res.length === 0) {
            return [];
        }
        for (const item of res) {
            ans.push(item);
        }
    }
    return ans;
};

[wychmod]

思路

思路上太难想通了，知道是拓扑排序，但是不知道组和组之间先建立关系，然后把组排出来，再排组内的。知道了要分组排，但是不知道怎么处理。看了代码明白了，先把组拓扑排序出来，然后再根据每个组，在组内进行拓扑排序。非常复杂。这个题过几天要重新做一下。

代码

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        def tp_sort(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

        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 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 = 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 = 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

复杂度分析

时间复杂度On+m 空间复杂度On+m

[JiangWenqi]

太难了，抄答案抄了半天

class Solution {
    private:
    vector<int> topoSort(vector<vector<int>>& graph, vector<int>& inDegrees, vector<int>& items) {
        queue<int> q;
        for (auto& item : items) {
            if (inDegrees[item] == 0) q.push(item);
        }
        vector<int> res;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            res.push_back(u);
            for (auto& v : graph[u]) {
                if (--inDegrees[v] == 0) q.push(v);
            }
        }
        return res.size() == items.size() ? res : vector<int>{};
    }

    public:
    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<int> groupDegree(n + m, 0);

        vector<vector<int>> itemGraph(n);
        vector<int> itemDegree(n, 0);

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

        int leftId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem[group[i]].push_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].push_back(i);
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].push_back(curGroupId);
                }
            }
        }

        vector<int> topoSortedGroup = topoSort(groupGraph, groupDegree, id);
        if (topoSortedGroup.size() == 0) {
            return vector<int>{};
        }
        vector<int> ans;
        for (auto& curGroupId : topoSortedGroup) {
            int size = groupItem[curGroupId].size();
            if (size == 0) continue;
            vector<int> res = topoSort(itemGraph, itemDegree, groupItem[curGroupId]);
            if (res.size() == 0) return vector<int>{};
            for (auto& item : res) ans.push_back(item);
        }

        return ans;
    }
};

O(m+n) O(m+n)

[liuguang520-lab]

思路

组间拓扑排序，组内拓扑排序

class Solution {
public:
    vector<int> topsort(vector<int>& degree, vector<vector<int>>& graph, vector<int>& items)
    {
        queue<int> Q;
        for(auto& a:items)
        {
            if(degree[a] == 0)
            {
                Q.push(a);
            }
        }
        vector<int> res;
        while(!Q.empty())
        {
            int cur_id = Q.front();
            Q.pop();
            res.emplace_back(cur_id);
            for(auto& u : graph[cur_id])
            {
                if(--degree[u] == 0)
                {
                    Q.push(u);
                }
            }
        }

        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>> itemsgraph(n);
        //组间和组内的度
        vector<int> groupdegree(n+m, 0);
        vector<int> itemsdegree(n, 0);

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

        //对无分组的项目进行编号；
        int left = m;
        for(int i = 0; i<n;i++)
        {
            if(group[i] == -1)
            {
                group[i] = left++;
            }
            groupitem[group[i]].emplace_back(i);
        }
        //建立图
        for(int i = 0; i< n;i++)
        {
            int cur_id = group[i];
            for(auto& item : beforeItems[i])
            {
                int pre = group[item];
                if(pre == cur_id)//同组
                {
                    itemsdegree[i] += 1;
                    itemsgraph[item].emplace_back(i);
                }
                else
                {
                    groupdegree[cur_id] +=1;
                    groupgraph[pre].emplace_back(cur_id);//组间关系
                }
            }
        }
        //首先需要对组间进行排序
        vector<int> grouptop = topsort(groupdegree, groupgraph, id);
        if(grouptop.size() == 0)
        {
            return vector<int>{};
        }
        //对组内进行排序
        vector<int> ans;
        for(auto& v : grouptop)
        {
            int size = groupitem[v].size();
            if(size == 0)
            {
                continue;
            }
            vector<int> itemtop = topsort(itemsdegree, itemsgraph, groupitem[v]);
            if(itemtop.size() == 0)
            {
                return vector<int>{};
            }
            for(auto & w : itemtop)
            {
                ans.emplace_back(w);
            }
        }   
        return ans;
    }
};

复杂度分析

• 时间复杂度O(N +M)
• 空间复杂度O(N+M)

[zhishinaigai]

看不懂，下次一定

代码

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;
    }
};

[biscuit279]

不明觉厉

class Solution:
    def tp_sort(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], 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

时间复杂度：O（m+n） 空间复杂度：O(m+n)

[yinhaoti]

# 笑死，大家都是下次一定，我也

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

        while q:
            vertex = q.popleft()
            ans.append(vertex)

            for neighbor in neighbors[vertex]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)
        return ans

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        """
        Keywords: beforeItems -> come before ith item
        Ideas: topological sort
        TC:
        SC:
        """

        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)
        group_projects = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        project_neighbors = 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)

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        ans = []
        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

[miss1]

看不懂，下次一定

class Solution:
    def tp_sort(self, items: int, pres: List[List[int]]) -> List[int]:
        res = []
        visited = [0] * items
        adjacent = [[] for _ in range(items)]

        def dfs(i):
            if visited[i] == 1:
                return False
            if visited[i] == 2:
                return True
            visited[i] = 1
            for j in adjacent[i]:
                if not dfs(j):
                    return False

            visited[i] = 2
            res.append(i)
            return True
        for cur, pre in pres:
            adjacent[cur].append(pre)
        for i in range(items):
            if not dfs(i):
                return []
        return res

[LQyt2012]

思路

拓扑排序

代码

class Solution:
    def topological_sort(self,items,indegree,neighbors):
        # 建立队列和访问顺序
        queue = collections.deque()
        res = []

        # 初始化队列
        for item in items:
            if not indegree[item]:
                queue.append(item)

        if not queue: return []

        # BFS
        while queue:
            cur = queue.popleft()
            res.append(cur)

            # 遍历邻居节点
            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    queue.append(neighbor)

        return res

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

        task_indegree = [0] * n    
        group_indegree = [0] * max_group_id
        task_neighbors = [[] for _ in range(n)]
        group_neighbors = [[] for _ in range(max_group_id)]
        group_to_tasks = [[] for _ in range(max_group_id)]

        for task in range(n):
            group_to_tasks[group[task]].append(task)

            for prerequisite in beforeItems[task]:

                # 判断相关联的两个项目是否属于同一组
                if group[prerequisite] != group[task]:

                    # 不是同组，给小组建图
                    group_indegree[group[task]] += 1
                    group_neighbors[group[prerequisite]].append(group[task])
                else:
                    # 同组，给组内项目建图
                    task_indegree[task] += 1
                    task_neighbors[prerequisite].append(task)

        res = []

        # 得到小组的访问顺序
        group_queue = self.topological_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:
            # 得到每组项目的访问顺序
            task_queue = self.topological_sort(group_to_tasks[group_id],task_indegree,task_neighbors)

            if len(task_queue) != len(group_to_tasks[group_id]):
                return []
            res += task_queue

        return res

复杂度分析

时间复杂度：O(M+N)
空间复杂度：O(M+N)

[freedom0123]

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>[] 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<>();
        }

        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]++;
            }
        }

        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];
        }

        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        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<>();
    }
}

[tensorstart]

不会

抄的

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
const topSort = (deg, graph, items) => {
    const Q = [];
    for (const item of items) {
        if (deg[item] === 0) {
            Q.push(item);
        }
    }
    const res = [];
    while (Q.length) {
        const u = Q.shift(); 
        res.push(u);
        for (let i = 0; i < graph[u].length; ++i) {
            const v = graph[u][i];
            if (--deg[v] === 0) {
                Q.push(v);
            }
        }
    }
    return res.length == items.length ? res : [];
}

var sortItems = function(n, m, group, beforeItems) {
    const groupItem = new Array(n + m).fill(0).map(() => []);

    // 组间和组内依赖图
    const groupGraph = new Array(n + m).fill(0).map(() => []);
    const itemGraph = new Array(n).fill(0).map(() => []);

    // 组间和组内入度数组
    const groupDegree = new Array(n + m).fill(0);
    const itemDegree = new Array(n).fill(0);

    const id = new Array(n + m).fill(0).map((v, index) => index);

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

    // 组间拓扑关系排序
    const groupTopSort = topSort(groupDegree, groupGraph, id); 
    if (groupTopSort.length == 0) {
        return [];
    } 
    const ans = [];
    // 组内拓扑关系排序
    for (const curGroupId of groupTopSort) {
        const size = groupItem[curGroupId].length;
        if (size == 0) {
            continue;
        }
        const res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
        if (res.length === 0) {
            return [];
        }
        for (const item of res) {
            ans.push(item);
        }
    }
    return ans;
};

[lizimu0709]

思路 有点难了……直接看的题解 使用拓扑排序，而且使用两层topo排序

public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<List<Integer>> groupItem = new ArrayList<>();//项目分组
        for(int i = 0;i < n + m;i++){//初始化小组
            groupItem.add(new ArrayList<>());
        }
            int gId = m;//新的组号从m开始
        for(int i = 0;i < group.length;i++){
            if(group[i] == -1)group[i] = gId++;//没有id的加上组id
            groupItem.get(group[i]).add(i);//同一组的放在一起
        }
        List<List<Integer>> graphInGroup = new ArrayList<>();//组内拓扑关系
        List<List<Integer>> graphOutGroup = new ArrayList<>();//组间拓扑关系
        for(int i = 0;i < n + m;i++){//初始化拓扑关系
            graphOutGroup.add(new ArrayList<>());
            if(i >= n)continue;
            graphInGroup.add(new ArrayList<>());
        }
        List<Integer> groupId = new ArrayList<>();//所有组id
        for(int i = 0;i < n + m;i++){
            groupId.add(i);
        }
            // 需要拓扑排序 所以结点的入度必不可少 两个数组分别维护不同结点的入度
        int[] degInGroup = new int[n];//组内 结点入度 （组内项目入度）
        int[] degOutGroup = new int[n + m];//组间 结点入度（小组入度）

        for(int i = 0;i < beforeItems.size();i++){//遍历关系
            int curGroupId = group[i];//当前项目i所属的小组id
            List<Integer> beforeItem = beforeItems.get(i);
            for(Integer item : beforeItem){
                if(group[item] == curGroupId){//同一组 修改组内拓扑
                    degInGroup[i]++;// 组内结点的入度+1
                    graphInGroup.get(item).add(i);//item 在 i之前
                }else{
                    degOutGroup[curGroupId]++;// 小组间的结点入度 + 1
                    graphOutGroup.get(group[item]).add(curGroupId);// group[item] 小组 在 curGroupId 之前
                }
            }
        }
            //组间拓扑排序，也就是小组之间的拓扑排序，需要的参数 小组结点的入度degOutGroup，所有的小组groupId，组间的拓扑关系图graphOutGroup
        List<Integer> outGroupTopSort = topSort(degOutGroup,groupId,graphOutGroup);
        if(outGroupTopSort.size() == 0)return new int[0];//无法拓扑排序 返回

        int[] res = new int[n];
        int index = 0;
        for(Integer gid : outGroupTopSort){//遍历排序后的小组id
            List<Integer> items = groupItem.get(gid);//根据小组id 拿到这一小组中的所有成员
            if(items.size() == 0)continue;
            //组内拓扑排序，需要的参数 组内结点的入度degInGroup，组内的所有的结点groupItem.get(gid)，组内的拓扑关系图graphInGroup
            List<Integer> inGourpTopSort = topSort(degInGroup,groupItem.get(gid),graphInGroup);
            if(inGourpTopSort.size() == 0)return new int[0];//无法拓扑排序 返回
            for(int item : inGourpTopSort){//排序后，依次的放入答案集合当中
                res[index++] = item;
            }
        }
        return res;
    }

    public List<Integer> topSort(int[] deg, List<Integer> items,List<List<Integer>> graph){
        Queue<Integer> queue = new LinkedList<>();
        for(Integer item:items){
            if(deg[item] == 0)queue.offer(item);
        }
        List<Integer> res = new ArrayList<>();
        while(!queue.isEmpty()){
            int cur = queue.poll();
            res.add(cur);
            for(int neighbor: graph.get(cur)){
                if(--deg[neighbor] == 0){
                    queue.offer(neighbor);
                }
            }
        }
        return res.size() == items.size() ? res : new ArrayList<>();
    }

时间复杂度O(N +M) 空间复杂度O(N+M)

[hyh331]

Day31 思路

太难了，抄的，哈哈哈

class Solution {
public:
    using UMIV = unordered_map<int, vector<int> >;
    using UMII = unordered_map<int, int>;
    using VVI = vector<vector<int> >;
    using VI = vector<int>;
    // 保存小组内 可执行的任务序列
    UMIV sub;
    // n个项目， m个小组
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& befores) {
        // 如果任务不属于任何小组，说明该任务可以独属一组，给该任务新建一个虚拟组
        // 可直接加入到sub中，不必走后面的组内拓扑排序
        for (int j = 0; j < n; j++) {
            // 把组号为-1的重新编号，从m开始
            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;
    }

    // 比较常规的topo排序代码
    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;
        // 入度为0的节点加入队列
        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中
        sub[gpid] = move(res);
        return sub[gpid].size() == n;
    }
};

复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(m+n)

[KelvinG-LGTM]

思路

过两天回头再来看看.

代码

#空空如也

[ShuqianYang]

第一天打卡 好难不会做

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def tp_sort(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], 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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n+m)$
• 空间复杂度：$O(n+m)$

[AConcert]

var sortItems = function(n, m, group, beforeItems) {
    const grahG = [], degG = new Uint16Array(n + m), idsG = [], 
          grahI = [], degI = new Uint16Array(n), idsI = [], r = []
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            idsG[m] = m 
            group[i] = m++
        } else idsG[group[i]] = group[i]
        if (!idsI[group[i]]) idsI[group[i]] = [] 
        idsI[group[i]].push(i)
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < beforeItems[i].length; j++) {
            const itemI = beforeItems[i][j]
            if (group[i] === group[itemI]) {
                degI[i]++
                if (!grahI[itemI]) grahI[itemI] = []
                grahI[itemI].push(i)
            } else {
                degG[group[i]]++
                if (!grahG[group[itemI]]) grahG[group[itemI]] = []
                grahG[group[itemI]].push(group[i])
            }
        }
    }
    const idsGS = sort(idsG.filter(v => v !== void 0), grahG, degG) 
    if (idsGS.length === 0) return []
    for (let i = 0; i < idsGS.length; i++) {
        if (!idsI[idsGS[i]]) continue
        const idsIS = sort(idsI[idsGS[i]], grahI, degI)
        if (idsIS.length === 0) return []
        r.push(...idsIS)
    }
    return r
};
const sort = (ids, grah, deg) => {
    const q = [], r = []
    let start = 0
    for (let i = 0; i < ids.length; i++) if (deg[ids[i]] === 0) q.push(ids[i])
    while (start < q.length) {
        const n = q[start++]
        r.push(n)
        if (!grah[n]) continue
        for (let i = 0; i < grah[n].length; i++) if (--deg[grah[n][i]] === 0) q.push(grah[n][i])
    }
    return r.length === ids.length ? r : []
}

[mo660]

不会写明天再看

class Solution:
    def tp_sort(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], 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

[Joyce94]

算法流程 1、给-1的项目分组 2、得到小组关系图（分组情况、组的邻接表、入度表）、项目关系图（项目的邻接表、入度表） 3、bfs得到组的顺序 4、分组进行bfs，得到组内的排序

class Solution:
    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 item in beforeItems[project]:
                if group[item] != group[project]:   ## 小组关系图 
                    group_indegree[group[project]] += 1 
                    group_neighbors[group[item]].append(group[project]) 
                else:       ## 项目关系图 
                    project_indegree[project] += 1 
                    project_neighbors[item].append(project) 

        res = [] 
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)   
        # 组的顺序 [0, 1, 2, 4, 3]
        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 [] 
            res += project_queue
        return res 

    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:      ## 得到入度序列 
            if item not in indegree:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: 
                    q.append(neighbor) 
        return ans 

[weihaoxie]

思路

难度比较大，参考题解

代码

class Solution:
    def tp_sort(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], 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

复杂度

• 时间复杂度O(m+n)
• 空间复杂度O(m+n)

[ghost]

class Solution:
    def topological_sort(self,items,indegree,neighbors):
        # 建立队列和访问顺序
        queue = collections.deque()
        res = []

        # 初始化队列
        for item in items:
            if not indegree[item]:
                queue.append(item)

        if not queue: return []

        # BFS
        while queue:
            cur = queue.popleft()
            res.append(cur)

            # 遍历邻居节点
            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    queue.append(neighbor)

        return res

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

        task_indegree = [0] * n    
        group_indegree = [0] * max_group_id
        task_neighbors = [[] for _ in range(n)]
        group_neighbors = [[] for _ in range(max_group_id)]
        group_to_tasks = [[] for _ in range(max_group_id)]

        for task in range(n):
            group_to_tasks[group[task]].append(task)

            for prerequisite in beforeItems[task]:

                # 判断相关联的两个项目是否属于同一组
                if group[prerequisite] != group[task]:

                    # 不是同组，给小组建图
                    group_indegree[group[task]] += 1
                    group_neighbors[group[prerequisite]].append(group[task])
                else:
                    # 同组，给组内项目建图
                    task_indegree[task] += 1
                    task_neighbors[prerequisite].append(task)

        res = []

        # 得到小组的访问顺序
        group_queue = self.topological_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:
            # 得到每组项目的访问顺序
            task_queue = self.topological_sort(group_to_tasks[group_id],task_indegree,task_neighbors)

            if len(task_queue) != len(group_to_tasks[group_id]):
                return []
            res += task_queue

        return res

时间复杂度O(m+n) 空间复杂度O(m+n)

[ShirAdaOne]

思路

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

代码

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<List<Integer>> groupItem = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupItem.add(new ArrayList<Integer>());
        }

        List<List<Integer>> groupGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupGraph.add(new ArrayList<Integer>());
        }
        List<List<Integer>> itemGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; ++i) {
            itemGraph.add(new ArrayList<Integer>());
        }

        int[] groupDegree = new int[n + m];
        int[] itemDegree = new int[n];

        List<Integer> id = new ArrayList<Integer>();
        for (int i = 0; i < n + m; ++i) {
            id.add(i);
        }

        int leftId = m;
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem.get(group[i]).add(i);
        }
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (int item : beforeItems.get(i)) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph.get(item).add(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph.get(beforeGroupId).add(curGroupId);
                }
            }
        }

        List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return new int[0];
        }
        int[] ans = new int[n];
        int index = 0;
        for (int curGroupId : groupTopSort) {
            int size = groupItem.get(curGroupId).size();
            if (size == 0) {
                continue;
            }
            List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
            if (res.size() == 0) {
                return new int[0];
            }
            for (int item : res) {
                ans[index++] = item;
            }
        }
        return ans;
    }

    public List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int item : items) {
            if (deg[item] == 0) {
                queue.offer(item);
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            int u = queue.poll(); 
            res.add(u);
            for (int v : graph.get(u)) {
                if (--deg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return res.size() == items.size() ? res : new ArrayList<Integer>();
    }
}

复杂度分析

• 时间复杂度：O(n+m)
• 空间复杂度：O(n+m)

[revisegoal]

拓扑排序

以临界矩阵创建有向图，使用拓扑排序处理

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public 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>[] 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<>();
        }

        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]++;
            }
        }

        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];
        }
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }
        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<>();
    }
}

• time: O(m + n)
• space: O(m + n)

[flaming-cl]

var sortItems = function(n, m, group, beforeItems) {
    const grahG = [], degG = new Uint16Array(n + m), idsG = [], 
          grahI = [], degI = new Uint16Array(n), idsI = [], r = []
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            idsG[m] = m 
            group[i] = m++
        } else idsG[group[i]] = group[i]
        if (!idsI[group[i]]) idsI[group[i]] = [] 
        idsI[group[i]].push(i)
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < beforeItems[i].length; j++) {
            const itemI = beforeItems[i][j]
            if (group[i] === group[itemI]) {
                degI[i]++
                if (!grahI[itemI]) grahI[itemI] = []
                grahI[itemI].push(i)
            } else {
                degG[group[i]]++
                if (!grahG[group[itemI]]) grahG[group[itemI]] = []
                grahG[group[itemI]].push(group[i])
            }
        }
    }
    const idsGS = sort(idsG.filter(v => v !== void 0), grahG, degG) 
    if (idsGS.length === 0) return []
    for (let i = 0; i < idsGS.length; i++) {
        if (!idsI[idsGS[i]]) continue
        const idsIS = sort(idsI[idsGS[i]], grahI, degI)
        if (idsIS.length === 0) return []
        r.push(...idsIS)
    }
    return r
};
const sort = (ids, grah, deg) => {
    const q = [], r = []
    let start = 0
    for (let i = 0; i < ids.length; i++) if (deg[ids[i]] === 0) q.push(ids[i])
    while (start < q.length) {
        const n = q[start++]
        r.push(n)
        if (!grah[n]) continue
        for (let i = 0; i < grah[n].length; i++) if (--deg[grah[n][i]] === 0) q.push(grah[n][i])
    }
    return r.length === ids.length ? r : []
}

[sallyrubyjade]

思路

拓扑排序

代码

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
var sortItems = function(n, m, group, beforeItems) {
    const grahG = [], degG = new Uint16Array(n + m), idsG = [], 
          grahI = [], degI = new Uint16Array(n), idsI = [], r = []
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            idsG[m] = m 
            group[i] = m++
        } else idsG[group[i]] = group[i]
        if (!idsI[group[i]]) idsI[group[i]] = [] 
        idsI[group[i]].push(i)
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < beforeItems[i].length; j++) {
            const itemI = beforeItems[i][j]
            if (group[i] === group[itemI]) {
                degI[i]++
                if (!grahI[itemI]) grahI[itemI] = []
                grahI[itemI].push(i)
            } else {
                degG[group[i]]++
                if (!grahG[group[itemI]]) grahG[group[itemI]] = []
                grahG[group[itemI]].push(group[i])
            }
        }
    }
    const idsGS = sort(idsG.filter(v => v !== void 0), grahG, degG) 
    if (idsGS.length === 0) return []
    for (let i = 0; i < idsGS.length; i++) {
        if (!idsI[idsGS[i]]) continue
        const idsIS = sort(idsI[idsGS[i]], grahI, degI)
        if (idsIS.length === 0) return []
        r.push(...idsIS)
    }
    return r
};
const sort = (ids, grah, deg) => {
    const q = [], r = []
    let start = 0
    for (let i = 0; i < ids.length; i++) if (deg[ids[i]] === 0) q.push(ids[i])
    while (start < q.length) {
        const n = q[start++]
        r.push(n)
        if (!grah[n]) continue
        for (let i = 0; i < grah[n].length; i++) if (--deg[grah[n][i]] === 0) q.push(grah[n][i])
    }
    return r.length === ids.length ? r : []
}

[maggiexie00]

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

# Helper function: returns topological order of a graph, if it exists.
def get_top_order(graph, indegree):
    top_order = []
    stack = [node for node in range(len(graph)) if indegree[node] == 0]
    while stack:
        v = stack.pop()
        top_order.append(v)
        for u in graph[v]:
            indegree[u] -= 1
            if indegree[u] == 0:
                stack.append(u)
    return top_order if len(top_order) == len(graph) else []

# STEP 1: Create a new group for each item that belongs to no group. 
for u in range(len(group)):
    if group[u] == -1:
        group[u] = m
        m+=1

# STEP 2: Build directed graphs for items and groups.
graph_items = [[] for _ in range(n)]
indegree_items = [0] * n
graph_groups = [[] for _ in range(m)]
indegree_groups = [0] * m        
for u in range(n):
    for v in beforeItems[u]:                
        graph_items[v].append(u)
        indegree_items[u] += 1
        if group[u]!=group[v]:
            graph_groups[group[v]].append(group[u])
            indegree_groups[group[u]] += 1                    

# STEP 3: Find topological orders of items and groups.
item_order = get_top_order(graph_items, indegree_items)
group_order = get_top_order(graph_groups, indegree_groups)
if not item_order or not group_order: return []

# STEP 4: Find order of items within each group.
order_within_group = collections.defaultdict(list)
for v in item_order:
    order_within_group[group[v]].append(v)

# STEP 5. Combine ordered groups.
res = []
for group in group_order:
    res += order_within_group[group]
return res

[duke-github]

思路

拓扑排序

复杂度

时间复杂度：O(V + E) 空间复杂度：O(m + n*n)

代码

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<>();
    }
}

[flyzenr]

• 思路

  • 从问题的描述（任务计划安排）和结果要求（有可能不存在，如果有，可能不唯一），可以看出思路是「拓扑排序」

• Code - 图+拓扑排序

  -

        class Solution:
            def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
                # 给每个未分组的项目分组
                for i in range(n):
                    if group[i] == -1:
                        group[i] = m
                        m += 1
                # graph和indegree存储整个项目的图，其中graph存储有向边，indegree存储每个项目的入度
                graph = [[] for _ in range(n)]
                indegree = [0] * n
                # groupid存储所有的小组以及每个小组所属的项目，用字典key表示项目，values表示属于该小组的项目
                groupid = collections.defaultdict(list)
                # graph1和indgreetemp存储小组的图以及每个小组的入度，由于下面的统计方法肯定会有重复边出现，所以后面会去重
                graph1 =collections.defaultdict(list)
                indegreetemp = collections.defaultdict(list)
                # 遍历每个项目，以及该项目的前置项目，构建小组图和整个项目图
                for i in range(n):
                    for j in beforeItems[i]:
                        graph[j].append(i)
                        graph1[group[j]].append(group[i])
                    indegree[i] = len(beforeItems[i])
                    indegreetemp[group[i]].extend([group[w] for w in beforeItems[i]])
                    groupid[group[i]].append(i)
                # 对小组图存储有向边的graph1进行去重，统计每个小组的入度存储到indegree1
                graph1 = {i: list(set(graph1[i])) for i in groupid.keys()}
                indegree1 = {i: len(set(indegreetemp[i])-set([i])) for i in groupid.keys()}
                # 拓扑排序函数，给一个有向图，返回其拓扑排序，如果存在环，即不能拓扑排序，返回空列表
                # 其中indegree代表入度，graph代表有向边，items代表该图的每一个顶点
                def topolopy(indegree, graph, items):
                    q = []
                    res = []
                    for i in items:
                        if indegree[i] == 0:
                            q.append(i)
                    while q:
                        node = q.pop(0)
                        res.append(node)
                        for i in graph[node]:
                            indegree[i] -= 1
                            if i in items and indegree[i] == 0:
                                q.append(i)
                    return [] if len(res) != len(items) else res
  
                sol = []
                # 对小组组成图进行拓扑排序，返回小组的排序数组，存到order
                order = topolopy(indegree1, graph1, list(groupid.keys()))
                if len(order) == 0:
                    return []
                # 对order中的每个小组所属项目构成的图进行拓扑排序，得到的结果存储到最后的答案sol中
                for i in order:
                    temp = topolopy(indegree, graph, groupid[i])
                    if len(temp) > 0:
                        sol.extend(temp)
                    else:
                        return []
                return sol

• 复杂度

  • 时间复杂度: $O(m+n^2+E{Group}+E{item})$ ，n是数组的长度
  • 空间复杂度 $O(m+n^2)$

[taojin1992]

/*
Plan:

one indegree array/map for project
one indegree array/map for group

m groups: 0-(m-1)
n items: 0-(n-1)

when a group == -1, start from m, increment its group id

5
3
[0,0,2,1,0]
[[3],[],[],[],[1,3,2]]

[3,2,0,1,4]

5
3
[0,0,2,1,0]
[[3],[],[],[],[1,3,2]]
-> [3,2,0,1,4]

do not double count duplicate edges for in-degree

Time: O(2*n) + O(maxGroupID) + O(n + number of pres) + O(maxGroupID) + O(number of groups + number of group edges) + O(number of item + number of item edge)

Space: 
output: O(n)
Map<Integer, Set<Integer>> groupProjectsMapping: O(n)
Map<Integer, Set<Integer>> projectIndegree: O(n + edges between item)
Map<Integer, Set<Integer>> groupIndegree: O(group num + edge between group)
Map<Integer, Set<Integer>> groupsGraph: O(group num + edge between group), edge between group bounded by number of pres
Map<Integer, Set<Integer>> projectsGraph: O(n + edges between item)
Set<Integer> groupNodes: O(maxGroupID)
Set<Integer> targetNodes: O(n)
*/

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int maxGroupID = m;
        // reassign the group id given -1, -1 means an item stands on its own
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = maxGroupID;
                maxGroupID++;
            }
        }

        // assign each project to each group
        // group -> set of projects
        //  & populate: 
        // one indegree array for project
        // one indegree array for group
        // & build 2 graphs: projects (pre) / groups -> neighbors 小组关系图 + 项目关系图

        Map<Integer, Set<Integer>> groupProjectsMapping = new HashMap<>();

        // project - indegree mapping
        // do not double count duplicate edges for in-degree, that's why i don't use int[] here
        Map<Integer, Set<Integer>> projectIndegree = new HashMap<>(); // max n size
        for (int i = 0; i < n; i++) {
            projectIndegree.put(i, new HashSet<>());
        }
        Map<Integer, Set<Integer>> groupIndegree = new HashMap<>(); // maxGroupID size
        for (int i = 0; i < maxGroupID; i++) {
            groupIndegree.put(i, new HashSet<>());
        }

        Map<Integer, Set<Integer>> groupsGraph = new HashMap<>();
        Map<Integer, Set<Integer>> projectsGraph = new HashMap<>();

        for (int p = 0; p < n; p++) {
            int groupID = group[p];
            if (!groupProjectsMapping.containsKey(groupID)) {
                groupProjectsMapping.put(groupID, new HashSet<Integer>());
            }
            groupProjectsMapping.get(groupID).add(p);

            // we can check the pre for each project
            List<Integer> presOfP = beforeItems.get(p);
            for (int preOfP : presOfP) {
                int groupOfPre = group[preOfP];
                int groupOfP = group[p];

                // pre and p are not in the same group
                if (groupOfPre != groupOfP) { // self-loop excluded
                    // pre's group goes before p's group, pre's group -> p's group

                    groupIndegree.get(groupOfP).add(groupOfPre);
                    if (!groupsGraph.containsKey(groupOfPre)) {
                        groupsGraph.put(groupOfPre, new HashSet<Integer>());
                    }
                    groupsGraph.get(groupOfPre).add(groupOfP);
                } 
                // pre and p are in the same group
                // 因为属于不同group的project，indegree不影响，所以如果pre和project在不同group，不需要更新project indegree（我之前问的else地方想明白了，# 项目关系图处）。
                else { //最后按group，分别sort，然后append结果。所以project之间关系仅针对同一group更新即可
                    projectIndegree.get(p).add(preOfP);
                    if (!projectsGraph.containsKey(preOfP)) {
                        projectsGraph.put(preOfP, new HashSet<Integer>());
                    }
                    projectsGraph.get(preOfP).add(p);// inside projectsGraph, of course, neighbors are from the same group
                }
            }
        }

        //System.out.println(groupIndegree);

        // after extracting all the info, call topological sorting on group
        Set<Integer> groupNodes = new HashSet<>();
        for (int i = 0; i < maxGroupID; i++) {
            groupNodes.add(i);
        }

        List<Integer> sortGroupRes = topologicalSort(groupNodes, groupIndegree, groupsGraph);

       // System.out.println(sortGroupRes);

        if (sortGroupRes.size() != maxGroupID) {
            return new int[0];
        }

        int[] sortRes = new int[n];
        int index = 0;

        // topological sort every single group
        for (int groupID : sortGroupRes) {
            Set<Integer> targetNodes = groupProjectsMapping.get(groupID);
            if (targetNodes == null) continue; //A group can have no item belonging to it.
            List<Integer> sortProjects = topologicalSort(targetNodes, projectIndegree, projectsGraph);

            if (sortProjects.size() != targetNodes.size()) {
                return new int[0];
            }
            for (int each : sortProjects) {
                sortRes[index++] = each;
            }
        }
        return sortRes;
    }

    // topological sort
    private List<Integer> topologicalSort(Set<Integer> selectedNodes,  Map<Integer, Set<Integer>> indegree, Map<Integer, Set<Integer>> graph) {
        List<Integer> sortRes = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int id : selectedNodes) {
            if (indegree.get(id).size() == 0) {
                queue.offer(id);
            }
        }
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            sortRes.add(curNode);
            Set<Integer> neighbors = graph.get(curNode); 
            if (neighbors != null) {
                for (int neighbor : neighbors) {

                    indegree.get(neighbor).remove(curNode);
                    if (indegree.get(neighbor).size() == 0) {
                        queue.offer(neighbor);
                    }

                }
            }
        }
        return sortRes;
    }

}

[ZacheryCao]

Code

class Solution:
    def tp_sort(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], 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

[XXjo]

代码

//拓扑排序
var topSort = function(inDegree, graph, items){
    let q = [];
    let res = [];
    for(let item of items){
        //入度为0，则加入q
        if(inDegree[item] === 0){
            q.push(item);
        }
    }
    while(q.length > 0){
        let cur = q.shift();
        res.push(cur);
        //删除与cur相邻的边，如果去掉相关边之后入度为0，则加入q
        for(let point of graph[cur]){
            inDegree[point] -= 1;
            if(inDegree[point] === 0){
                q.push(point);
            }
        }
    }
    return  res;
}

var sortItems = function(n, m, group, beforeItems) {
    let groupItem = new Array(n + m).fill(0).map(() => []);

    let groupGraph = new Array(n + m).fill(0).map(() => []);
    let itemGraph = new Array(n).fill(0).map(() => []);
    let groupInDegree = new Array(n + m).fill(0);
    let itemInDegree = new Array(0).fill(0);

    let id = new Array(n + m).fill(0).map((val, index) => index);
    //给未分配组的项目分配groupId，起始groupId为m
    for(let i = 0; i < n; i++){
        if(group[i] === -1){
            group[i] = m + i;
        }
        groupItem[group[i]].push(i);
    }

    //根据依赖关系建图
    for(let i = 0; i < n; i++){
        let curGroupId = group[i];
        for(let item of beforeItems[i]){
            let beforeGroupId = group[item];
            if(beforeGroupId === curGroupId){
                itemInDegree[i] += 1;
                itemGraph[item].push(i);
            }
            else{
                groupInDegree[curGroupId] += 1;
                groupGraph[beforeGroupId].push(curGroupId);
            }
        }
    }

    let groupTopsort = topSort(groupInDegree, groupGraph, id);
    if(groupTopsort.length === 0){
        return [];
    } 

    let res = [];
    for(let curGroupId of groupTopsort){
        let size = groupItem[curGroupId].length;
        if(size === 0) continue;
        let itemTopSort = topSort(itemInDegree, itemGraph, groupItem[curGroupId]);
        if(itemTopSort.length === 0){
            return [];
        } 
        for(let item of itemTopSort){
            res.push(item);
        }
    }

    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]
        """
        group_id = m;
        for i in range(n):
            if group[i] == -1:
                group[i] = group_id;
                group_id+=1;
        project_indegree = collections.defaultdict(int); 
        group_indegree = collections.defaultdict(int); 
        project_neighbor = collections.defaultdict(list);
        group_neighbor = collections.defaultdict(list); 
        group_project = collections.defaultdict(list);# {group1: project1, project2, project3...}

        for project in range(n):
            group_project[group[project]].append(project); 
            for before in beforeItems[project]:
                if group[before] != group[project]: #如果不属于同一个租
                    group_indegree[group[project]] += 1;
                    group_neighbor[group[before]].append(group[project]); 
                else: #同一个组，不同项目
                    project_indegree[project] += 1;
                    project_neighbor[before].append(project);
        res = [];
        queue = self.tp_sort([i for i in range(group_id)], group_indegree, group_neighbor); 
        if len(queue) != group_id:
            return [];
        for id in queue:
            project_queue = self.tp_sort(group_project[id], project_indegree,project_neighbor);
            if len(project_queue) != len(group_project[id]):
                return [];
            res += project_queue;
        return res;

    def tp_sort(self,items, indegree, neighbors): 
        queue = collections.deque();
        res = []; 
        for item in items:
            if not indegree[item]:
                queue.append(item);
        while queue:
            curr = queue.popleft();
            res.append(curr);
            for neighbor in neighbors[curr]:
                indegree[neighbor] -= 1;
                if not indegree[neighbor]:
                    queue.append(neighbor);
        return res;

    #time complexity: O(v+e);
    #space complexity; O(v+e); 

[KWDFW]

Day31

1203、项目管理

javascript #图

思路

1、拓扑排序

代码

const topSort = (deg, graph, items) => {
    const Q = [];
    for (const item of items) {
        if (deg[item] === 0) {
            Q.push(item);
        }
    }
    const res = [];
    while (Q.length) {
        const u = Q.shift(); 
        res.push(u);
        for (let i = 0; i < graph[u].length; ++i) {
            const v = graph[u][i];
            if (--deg[v] === 0) {
                Q.push(v);
            }
        }
    }
    return res.length == items.length ? res : [];
}

var sortItems = function(n, m, group, beforeItems) {
    const groupItem = new Array(n + m).fill(0).map(() => []);

    // 组间和组内依赖图
    const groupGraph = new Array(n + m).fill(0).map(() => []);
    const itemGraph = new Array(n).fill(0).map(() => []);

    // 组间和组内入度数组
    const groupDegree = new Array(n + m).fill(0);
    const itemDegree = new Array(n).fill(0);

    const id = new Array(n + m).fill(0).map((v, index) => index);

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

    // 组间拓扑关系排序
    const groupTopSort = topSort(groupDegree, groupGraph, id); 
    if (groupTopSort.length == 0) {
        return [];
    } 
    const ans = [];
    // 组内拓扑关系排序
    for (const curGroupId of groupTopSort) {
        const size = groupItem[curGroupId].length;
        if (size == 0) {
            continue;
        }
        const res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
        if (res.length === 0) {
            return [];
        }
        for (const item of res) {
            ans.push(item);
        }
    }
    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[gitbingsun]

题目地址(1203. 项目管理)

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

题目描述

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

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

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

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

 

示例 1：

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

前置知识

思路

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // assign group to item with -1 group
        for (int i = 0; i < group.size(); i++) {
            if (group[i] == -1) {
                group[i] = m++;
            }
        }

        // 组之间的邻接矩阵关系
        vector<vector<int>> groupAdj(m); 
        int groupIndegree[m]; 
        //建图和统计入度数组
        for (int i = 0; i < group.size(); i++) {
            // ith item's group is group[i]
            int curGroup = group[i];
            for (auto& j : beforeItems[i]) {
                int beforeItem = j;
                int beforeGroup = group[j];
                // beforeGroup --> curGroup 
                groupAdj[beforeGroup].push_back(curGroup);
                groupIndegree[curGroup]++;
            }
        }

        vector<vector<int>> itemAdj(n);
        int itemIndegree[n]; 
        //建图和统计入度数组
        for (int i = 0; i < n; i++) {
            for (auto& j : beforeItems[i]) {
                int beforeItem = j;
                itemAdj[beforeItem].push_back(i);
                itemIndegree[i]++;
            }
        }

        //组的拓扑排序
        vector<int> groupList = topologicalOrder(groupAdj, groupIndegree, m);
        if (groupList.size() == 0) return {}; 

        //项目的拓扑排序
        vector<int> itemList = topologicalOrder(itemAdj, itemIndegree, n);
        if (itemList.size() == 0) return {}; 

        //根据项目的拓扑排序，项目到组的多对一关系，建立组到项目的一对多关系
        map<int, vector<int>> group2Items;
        for(int i = 0; i < itemList.size(); i++) {
            group2Items[group[i]].push_back(i);
        }

        //把组的拓扑排序变为项目的拓扑排序
        vector<int> ret; 
        for (int g = 0; g < groupList.size(); g++) {
            vector<int> items = group2Items[g];
            ret.insert(ret.end(),items.begin(),items.end());
        }

        return ret;
    }

    vector<int> topologicalOrder(vector<vector<int>> adj, int indegree[], int nodeNum) {
        vector<int> ret;
        queue<int> q;
        for(int i = 0; i < nodeNum; i++) {
            if (indegree[i] == 0 ){
                q.push(i);
            }
        }
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            ret.push_back(cur);
            for (auto& successor : adj[cur]) {
                indegree[successor]--;
                if (indegree[successor] == 0) {
                    ret.push_back(successor);
                }
            }
        }
        if (ret.size() == nodeNum)
            return ret;
        else
            return {};
    }

};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n+m+Eitems+Egroups)$
• 空间复杂度：$O(n+m)$

[Magua-hub]

不会做...
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // assign group to item with -1 group
        for (int i = 0; i < group.size(); i++) {
            if (group[i] == -1) {
                group[i] = m++;
            }
        }

        // 组之间的邻接矩阵关系
        vector<vector<int>> groupAdj(m); 
        int groupIndegree[m]; 
        //建图和统计入度数组
        for (int i = 0; i < group.size(); i++) {
            // ith item's group is group[i]
            int curGroup = group[i];
            for (auto& j : beforeItems[i]) {
                int beforeItem = j;
                int beforeGroup = group[j];
                // beforeGroup --> curGroup 
                groupAdj[beforeGroup].push_back(curGroup);
                groupIndegree[curGroup]++;
            }
        }

        vector<vector<int>> itemAdj(n);
        int itemIndegree[n]; 
        //建图和统计入度数组
        for (int i = 0; i < n; i++) {
            for (auto& j : beforeItems[i]) {
                int beforeItem = j;
                itemAdj[beforeItem].push_back(i);
                itemIndegree[i]++;
            }
        }

        //组的拓扑排序
        vector<int> groupList = topologicalOrder(groupAdj, groupIndegree, m);
        if (groupList.size() == 0) return {}; 

        //项目的拓扑排序
        vector<int> itemList = topologicalOrder(itemAdj, itemIndegree, n);
        if (itemList.size() == 0) return {}; 

        //根据项目的拓扑排序，项目到组的多对一关系，建立组到项目的一对多关系
        map<int, vector<int>> group2Items;
        for(int i = 0; i < itemList.size(); i++) {
            group2Items[group[i]].push_back(i);
        }

        //把组的拓扑排序变为项目的拓扑排序
        vector<int> ret; 
        for (int g = 0; g < groupList.size(); g++) {
            vector<int> items = group2Items[g];
            ret.insert(ret.end(),items.begin(),items.end());
        }

        return ret;
    }

    vector<int> topologicalOrder(vector<vector<int>> adj, int indegree[], int nodeNum) {
        vector<int> ret;
        queue<int> q;
        for(int i = 0; i < nodeNum; i++) {
            if (indegree[i] == 0 ){
                q.push(i);
            }
        }
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            ret.push_back(cur);
            for (auto& successor : adj[cur]) {
                indegree[successor]--;
                if (indegree[successor] == 0) {
                    ret.push_back(successor);
                }
            }
        }
        if (ret.size() == nodeNum)
            return ret;
        else
            return {};
    }

};

[ShawYuan97]

思路

关键点

• 双重拓扑排序

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        def tp_sort(items, indegree, neighbors):
            """
            实现拓扑排序
            如果没有入度直接放入队列
            然后遍历队列，将没有入度的元素放入ans，然后将其邻居入度减一，如果此时入度为0，则可以加入队列
            直到整个队列为空
            """
            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
        # 首先处理没有分组的项目
        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)

        # 遍历n个项目
        for project in range(n):
            # 保存 组:[项目1,项目2,...,项目i]
            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 = 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 = 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

复杂度分析

令 n 为节点个数，e为边长。

• 时间复杂度：$O(n+e)$
• 空间复杂度：$O(n+e)$

[carterrr]

/**
 * @param n    项目数量
 * @param m    小组数量
 * @param group 项目被承接
 * @param beforeItems  项目依赖关系
 * @return
 */
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
    int idNext = m;
    List<List<Integer>> groupGraph = new ArrayList<>();//组间拓扑关系
    List<List<Integer>> inGroupGraph = new ArrayList<>();//组内拓扑关系
    List<Integer> groupId = new ArrayList<>();// 组id
    Map<Integer, List<Integer>> sameGroup = new HashMap<>();// 组id -> 组成员
    int id = m;
    for (int i = 0; i < group.length; i++) {
        if(group[i] == -1) group[i] = id++;
        sameGroup.getOrDefault(group[i], new ArrayList<>()).add(i);
    }
    for (int i = 0; i < n; i++) {
        groupId.add(i);
        inGroupGraph.add(new ArrayList<>()); // 组内 总共只有最多n个组需要考虑组内关系
        groupGraph.add(new ArrayList<>());
    }

    for (int i = n; i < n + m; i++) {
        groupGraph.add(new ArrayList<>());
        groupId.add(i);
    }
    int[] degInGroup = new int[n];
    int[] degOutGroup = new int[m + n];
    for (int i = 0; i < beforeItems.size(); i++) {
        int curGroupId = group[i];
        List<Integer> beforeItem = beforeItems.get(i);
        for (Integer bi : beforeItem) {
            if(group[bi] == curGroupId) {
                degInGroup[i] ++;
                inGroupGraph.get(bi).add(i);
            } else {
                degOutGroup[i] ++;
                groupGraph.get(group[bi]).add(curGroupId); 
            }
        }
    }

    List<Integer> outTop = topSort(degOutGroup, groupId, groupGraph); // 组间top排序
    if (outTop == null) return new int[0];
    int[] res = new int[n];
    int index = 0;
    for (Integer gid : outTop) {
        List<Integer> items = sameGroup.get(gid);
        if (items.size() == 0) continue;
        List<Integer> inTop = topSort(degInGroup, items, inGroupGraph);
        if(inTop == null) return new int[0];
        for (Integer i : inTop) {
            res[index ++] = i;
        }
    }
    return res;
}

public List<Integer> topSort(int[] indegree, List<Integer> items, List<List<Integer>> graph) {
    Queue<Integer> q = new LinkedList<>();
    for (Integer i : items) {
        if(indegree[i] == 0)
            q.offer(i);
    }
    List<Integer> res = new ArrayList<>();
    while(!q.isEmpty()) {
        Integer poll = q.poll();
        res.add(poll);
        List<Integer> nexts = graph.get(poll);
        for (Integer n : nexts) {
            if(--indegree[n] == 0) {
                q.offer(n);
            }
        }
    }
    return res.size() == indegree.length ? res : null;
}

[gitbingsun]

题目地址(1203. 项目管理)

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

题目描述

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

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

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

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

 

示例 1：

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

前置知识

• 思路

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        unordered_set<int> groupIds;
        unordered_map<int, unordered_set<int>>groupItems;
        int nextGroupId = m;
        for (int i=0; i<n; i++)
        {
            if (group[i]==-1)
            {
                group[i] = nextGroupId;
                nextGroupId += 1;
            }
            groupItems[group[i]].insert(i);
            groupIds.insert(group[i]);
        }

        // build graph inside each group 
        unordered_map<int, unordered_set<int>> adj; //6: 1,3,4
        unordered_map<int, int> indegree; // 6: 0, 1: 1
        for (int i = 0; i < n; i++) {
            for (auto j : beforeItems[i]) {
                // 同组内的item需要拓扑排序
                if (group[i] == group[j]) {
                    adj[j].insert(i);
                    indegree[i] += 1;
                }
            }
        }

        // 组内items排序
        unordered_map<int, vector<int>> groupItemsOrdered;
        for (auto i : groupItems) {
            int groupId = i.first;

            groupItemsOrdered[groupId] = topologicalSort(groupItems[groupId], adj, indegree);

            if (groupItemsOrdered[groupId].size() != groupItems[groupId].size()) {
                cout<<"return";
                return {};
            }
        }

        adj.clear();
        indegree.clear();
        // build graph among groups
        for (int i = 0; i < n; i++) {
            for (auto j : beforeItems[i]) {
                // 不同的组需要拓扑排序
                if (group[i] != group[j] && adj[group[j]].find(group[i]) == adj[group[j]].end()) {
                    adj[group[j]].insert(group[i]);
                    indegree[group[i]] += 1;
                }
            }
        }
        // 组之间拓扑排序
        unordered_set<int>groups;
        for (int i=0; i<n; i++) groups.insert(group[i]);
        vector<int>groupOrdered = topologicalSort(groups, adj, indegree);

        vector<int>rets;
        for (int groupId: groupOrdered)
        {
            for (auto node: groupItemsOrdered[groupId])
                rets.push_back(node);
        }
        return rets;
    }

    vector<int> topologicalSort(unordered_set<int>& nodes, unordered_map<int, unordered_set<int>>& next, unordered_map<int, int>& inDegree) {

        queue<int>q;
        vector<int>ret;
        for (auto node: nodes)
        {
            if (inDegree[node]==0)
                q.push(node);
        }
         while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            ret.push_back(cur);            
            for (auto next: next[cur] )
            {
                inDegree[next] -= 1;
                if (inDegree[next] == 0)
                    q.push(next);
            }
        }

        if (ret.size()==nodes.size())
            return ret;
        else
            return {};
    }

};

[xixiao51]

Idea

Topological sort for both groups and items

Code

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // add group number to isolation item
        for(int i = 0; i < group.length; i++) {
            if(group[i] == -1) {
                group[i] = m++;
            }
        }

        // create adjacency matrix for groups and items
        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<>();
        }

        // create indegree array for groups and items
        int[] groupIndegree = new int[m];
        int[] itemIndegree = new int[n];

        int len = group.length;
        for(int i = 0; i < len; i++) {
            int curGroup = group[i];
            for(Integer before: beforeItems.get(i)) {
                int beforeGroup = group[before];
                if(beforeGroup != curGroup) {
                    groupAdj[beforeGroup].add(curGroup);
                    groupIndegree[curGroup]++;
                }
            }
        }

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

        // use topologicalSort to sort groups and items
        List<Integer> itemsList = topologicalSort(itemAdj, itemIndegree, n);
        if(itemsList.size() == 0) {
            return new int[0];
        }

        List<Integer> groupList = topologicalSort(groupAdj, groupIndegree, m);
        if(groupList.size() == 0) {
            return new int[0];
        }

        // Build hashmap for groupsToItems
        // key：group，value：items in the group
        Map<Integer, List<Integer>> groupsToItems = new HashMap<>();
        for(Integer item : itemsList) {
            groupsToItems.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // Replace group number with itemList 
        List<Integer> ans = new ArrayList<>();
        for(int g: groupList) {
            ans.addAll(groupsToItems.getOrDefault(g, new ArrayList()));
        }

        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

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

        while(!q.isEmpty()) {
            int cur = q.poll();
            res.add(cur);
            for(int node: adj[cur]) {
                indegree[node]--;
                if(indegree[node] == 0) {
                    q.offer(node);
                }
            }
        }

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

Complexity Analysis

• Time complexity: O(m + n^2 + E(group) + E(item))
• Space complexity: O(m + n^2)