leetcode-pp / 91alg-5-daily-check

91 天学算法第五期打卡
55 stars 14 forks source link

【Day 31 】2021-10-10 - 1203. 项目管理 #48

Open azl397985856 opened 3 years ago

azl397985856 commented 3 years ago

1203. 项目管理

入选理由

暂无

题目地址

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

前置知识

公司共有 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] 不含重复元素

yanglr commented 3 years ago

思路:

方法: 拓扑排序

做两次拓扑排序

代码

实现语言: C++

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        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);
        }
        // 分别为两个组建图
        unordered_map<int, unordered_set<int>> next;
        unordered_map<int, int> inDegree;
        for (int i = 0; i < n; i++)
            for (int j : beforeItems[i])
            {
                if (group[i] != group[j])
                    continue;
                if (next[j].count(i) == 0)
                {
                    next[j].insert(i);
                    inDegree[i] += 1;
                }
            }
        // 分别得到两个组内的拓扑排序结果
        unordered_map<int, vector<int>> groupItemsOrdered;
        for (auto x : groupItems)
        {
            int groupId = x.first;
            groupItemsOrdered[groupId] = tpSort(groupItems[groupId], next, inDegree);
            if (groupItemsOrdered[groupId].size() != groupItems[groupId].size())
                return {};
        }
        // 建图并重新统计入度数组
        next.clear();
        inDegree.clear();
        for (int i = 0; i < n; i++)
            for (int j : beforeItems[i])
            {
                if (group[i] == group[j])
                    continue;
                if (next[group[j]].count(group[i]) == 0)
                {
                    next[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 = tpSort(groups, next, inDegree);

        vector<int> res;
        for (int groupId : groupOrdered)
        {
            for (auto node : groupItemsOrdered[groupId])
                res.push_back(node);
        }
        return res;
    }
    vector<int> tpSort(unordered_set<int>& nodes, unordered_map<int, unordered_set<int>>& next, unordered_map<int, int>& inDegree)
    {
        queue<int> q;
        vector<int> res;
        for (auto node : nodes)
        {
            if (inDegree[node] == 0)
                q.push(node);
        }
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            res.push_back(cur);
            for (auto next : next[cur])
            {
                inDegree[next] -= 1;
                if (inDegree[next] == 0)
                    q.push(next);
            }
        }
        if (res.size() == nodes.size())
            return res;
        return {};
    }
};

复杂度分析:

JiangyanLiNEU commented 3 years ago

Topological Sort

def sortItems(n, m, group, beforeItems):
    # set each -1 as a new group with group_id gi
    gi = max(group)
    for i in range(n):
        if group[i] < 0:
            gi += 1
            group[i] = gi

    # topo sort elements in "nodes"
    def topo(src, dst, nodes):
        q = [i for i in nodes if not src[i]]
        for x in q:
            for y in dst[x]:
                src[y].remove(x)
                if not src[y]:
                    q.append(y)
        return q if len(q) == len(nodes) else None

    # build DAG on group ids
    nodes = set(group)
    src, dst = {i: set() for i in nodes}, collections.defaultdict(set)
    for d in range(n):
        for s in beforeItems[d]:
            gd, gs = group[d], group[s]
            if gd != gs:
                src[gd].add(gs)
                dst[gs].add(gd)

    # topo sort group id
    group_order = topo(src, dst, nodes)
    if not group_order:
        return []

    # elements in each group
    g2i = collections.defaultdict(list)
    for i in range(n):
        g2i[group[i]].append(i)

    order = []
    for gid in group_order:
        # build DAG on elements in group[gid]
        nodes = g2i[gid]
        src, dst = {i: set() for i in nodes}, collections.defaultdict(set)
        for d in nodes:
            for s in beforeItems[d]:
                if s in nodes:
                    src[d].add(s)
                    dst[s].add(d)

        # topo sort elements in group[gid]
        in_group_order = topo(src, dst, nodes)
        if not in_group_order:
            return []
        order += in_group_order
    return order
falconruo commented 3 years ago

抄袭打卡先

思路:

代码 实现语言: C++

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        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);
        }
        // 分别为两个组建图
        unordered_map<int, unordered_set<int>> next;
        unordered_map<int, int> inDegree;
        for (int i = 0; i < n; i++)
            for (int j : beforeItems[i])
            {
                if (group[i] != group[j])
                    continue;
                if (next[j].count(i) == 0)
                {
                    next[j].insert(i);
                    inDegree[i] += 1;
                }
            }
        // 分别得到两个组内的拓扑排序结果
        unordered_map<int, vector<int>> groupItemsOrdered;
        for (auto x : groupItems)
        {
            int groupId = x.first;
            groupItemsOrdered[groupId] = tpSort(groupItems[groupId], next, inDegree);
            if (groupItemsOrdered[groupId].size() != groupItems[groupId].size())
                return {};
        }
        // 建图并重新统计入度数组
        next.clear();
        inDegree.clear();
        for (int i = 0; i < n; i++)
            for (int j : beforeItems[i])
            {
                if (group[i] == group[j])
                    continue;
                if (next[group[j]].count(group[i]) == 0)
                {
                    next[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 = tpSort(groups, next, inDegree);

        vector<int> res;
        for (int groupId : groupOrdered)
        {
            for (auto node : groupItemsOrdered[groupId])
                res.push_back(node);
        }
        return res;
    }
    vector<int> tpSort(unordered_set<int>& nodes, unordered_map<int, unordered_set<int>>& next, unordered_map<int, int>& inDegree)
    {
        queue<int> q;
        vector<int> res;
        for (auto node : nodes)
        {
            if (inDegree[node] == 0)
                q.push(node);
        }
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            res.push_back(cur);
            for (auto next : next[cur])
            {
                inDegree[next] -= 1;
                if (inDegree[next] == 0)
                    q.push(next);
            }
        }
        if (res.size() == nodes.size())
            return res;
        return {};
    }
};

复杂度分析: 时间复杂度:O(m + n^2),这里 n 是项目的总数,m 是组的总数 空间复杂度:O(m + n^2)

pophy commented 3 years ago

思路

Java Code

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        Map<Integer, Integer> indegreeMap = new HashMap();
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, List<Integer>> groupMap = new HashMap<>();
        Map<Integer, Integer> grpIndegreeMap = new HashMap();
        Map<Integer, List<Integer>> grpGraph = new HashMap<>();

        for (int i = 0; i < n; i++) {
            indegreeMap.put(i, 0);
            graph.put(i, new ArrayList<>());
        }

        int nextGrpId = m;
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = nextGrpId;
                nextGrpId++;
            }
            if (groupMap.get(group[i]) == null) {
                groupMap.put(group[i], new ArrayList<>());
            }
            groupMap.get(group[i]).add(i);
        }

        for (int i = 0; i < n; i++) {
            List<Integer> beforeList = beforeItems.get(i);
            if (beforeList != null) {
                for (Integer id : beforeList) {
                    if (group[i] == group[id]) {
                        indegreeMap.put(i, indegreeMap.get(i) + 1);
                        graph.get(id).add(i);
                    }
                }
            }
        }

        Map<Integer, List<Integer>> sortedGroupItemMap = new HashMap<>();
        for (int grpId : groupMap.keySet()) {
            List<Integer> sortedGroupItem = topoLogicSort(groupMap.get(grpId), indegreeMap, graph);
            if (sortedGroupItem.size() == 0) {
                return new int[0];
            }
            sortedGroupItemMap.put(grpId, sortedGroupItem);
        }

        for (int grpId : group) {
            grpIndegreeMap.put(grpId, 0);
        }

        for (int i = 0; i < n; i++) {
            List<Integer> beforeList = beforeItems.get(i);
            if (beforeList != null) {
                for (Integer id : beforeList) {
                    if (group[i] != group[id]) {
                        grpIndegreeMap.put(group[i], grpIndegreeMap.getOrDefault(group[i], 0) + 1);
                        if (grpGraph.get(group[id]) == null) {
                            grpGraph.put(group[id], new ArrayList<>());
                        }
                        grpGraph.get(group[id]).add(group[i]);
                    }
                }
            }
        }
        List<Integer> grpIDs = new ArrayList<>(grpIndegreeMap.keySet());
        List<Integer> sortedGrp = topoLogicSort(grpIDs, grpIndegreeMap, grpGraph);
        List<Integer> tempList = new ArrayList<>();
        for (int grpId : sortedGrp) {
            tempList.addAll(sortedGroupItemMap.get(grpId));
        }
        int[] res = new int[tempList.size()];
        for (int i = 0; i < tempList.size(); i++) {
            res[i] = tempList.get(i);
        }
        return res;
    }

    private List<Integer> topoLogicSort(List<Integer> items, Map<Integer, Integer> indegreeMap, Map<Integer, List<Integer>> graph) {
        Queue<Integer> q = new LinkedList<>();
        for (int id : items) {
            if (indegreeMap.get(id) == 0) {
                q.add(id);
            }
        }
        List<Integer> tempList = new ArrayList<>();

        while (!q.isEmpty()) {
            int curId = q.poll();
            tempList.add(curId);
            List<Integer> nextIDs = graph.get(curId);
            if (nextIDs != null) {
                for (Integer nextID : nextIDs) {
                    indegreeMap.put(nextID, indegreeMap.get(nextID) - 1);
                    if (indegreeMap.get(nextID) == 0) {
                        q.add(nextID);
                    }
                }
            }
        }
        if (tempList.size() != items.size()) {
            return new ArrayList<>();
        }
        return tempList;
    }
}

时间&空间

thinkfurther commented 3 years ago

思路

这一题目不是很熟,主要参考了解答。

拓扑排序是靠DFS,首先找到indegree为0的node,然后将其相邻节点的indegree-1,并将其加入queue

在为什么要进行两次排序的时候思考了很久,想清楚了。因为我们把任务分配给组的时候,引入了组的依赖关系。所以我们需要先排序有依赖关系的组,然后在组内排序项目的依赖。

其实我这里有疑问,这里可能会引入循环依赖。

代码

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, beforeItems):
        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 beforeItem in beforeItems[project]:
                if group[beforeItem] != group[project]:
                    group_indegree[group[project]] += 1
                    group_neighbors[group[beforeItem]].append(group[project])
                else:
                    project_indegree[project] += 1
                    project_neighbors[beforeItem].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(V+E)

空间复杂度:O(V+E)

zhangzz2015 commented 3 years ago

思路

关键点

代码

C++ Code:


class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {

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

        vector<vector<int>> graphGroup(m);
        vector<int> inorderGroup(m,0); 
        vector<vector<int>> graphItem(n);
        vector<int> inorderItem(n,0); 

        for(int i=0; i<group.size(); i++)
        {
                for(int j =0; j < beforeItems[i].size(); j++)
                {
                    if(group[beforeItems[i][j]] != group[i])
                    {
                       // graphGroup[group[i]].push_back(group[beforeItems[i][j]]);
                        graphGroup[group[beforeItems[i][j]]].push_back(group[i]); 
                        inorderGroup[group[i]]++; 
                      //  inorderGroup[group[beforeItems[i][j]]]++; 
                    }
                    //graphItem[i].push_back(beforeItems[i][j]);
                    //inorderItem[beforeItems[i][j]]++;
                    graphItem[beforeItems[i][j]].push_back(i);
                    inorderItem[i]++; 
                }
        }

        vector<int> groupOrder= topoOrder(graphGroup, inorderGroup); 
        if(groupOrder.size()==0)
            return vector<int>();
        vector<int> itemOrder = topoOrder(graphItem, inorderItem); 
        if(itemOrder.size()==0)
            return vector<int>();
        vector<vector<int>> groupSort(m); 
        for(int i=0; i< itemOrder.size(); i++)
        {
            groupSort[group[itemOrder[i]]].push_back(itemOrder[i]); 
        }
        vector<int> ret;
        for(int i=0; i< groupOrder.size(); i++)
        {
            for(int j=0; j< groupSort[groupOrder[i]].size(); j++)
            {
                ret.push_back(groupSort[groupOrder[i]][j]); 
            }
        }
        return ret; 

     }    
    vector<int> topoOrder(vector<vector<int>>& graph, vector<int>& inorder)
    {
        int node = graph.size(); 
        queue<int> que; 
        for(int i=0; i< node; i++)
        {
            if(inorder[i]==0)
            {
                que.push(i);
            }
        }
        vector<int> res; 
        while(que.size())
        {
            int isize =que.size(); 

            for(int i=0; i< que.size(); i++)
            {
                int topNode = que.front(); 
                que.pop(); 
                res.push_back(topNode); 
                for(int j=0; j < graph[topNode].size(); j++)
                {
                    int nextNode =graph[topNode][j]; 
                    inorder[nextNode]--; 
                    if(inorder[nextNode]==0)
                    {
                        que.push(nextNode); 
                    }
                }
            }
        }

        for(int i=0; i< node; i++)
        {
            if(inorder[i]!=0)
                return vector<int>(); 
        }
        return res; 
    }    
};
yachtcoder commented 3 years ago

没写完 占个坑有空了再来补全吧


class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        ggraph = defaultdict(list)
        indgr = defaultdict(int)
        gindgr = defaultdict(int)
        gps = defaultdict(set)
        for i in range(n):
            gps[group[i]].add(i)
        '''TODO:
        for unassigned task, assign a unique group id.
         build group dependency graph, if toposort toget an group order
         if group order is not toposortable, return []
         topsort the tasks for each group. get a project order
         finally, using the group order, output the project of each group.
        '''
        for i in range(n):
            for p in beforeItems[i]:
                graph[p].append(i)
                indgr[i] += 1
        queue = deque()
        for i in range(n):
            if indgr[i] == 0:
                queue.append(i)
        ret = []
        while queue:
            node = queue.popleft()
            ret.append([group[node],node])
            for i in graph[node]:
                indgr[i] -= 1
                if indgr[i] == 0:
                    queue.append(i)
        if len(ret) == n:
            return ret
        return []
···
wangzehan123 commented 3 years ago

class Solution {
       public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        //不属于任何组的任务指派个独立组id
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        List<Set<Integer>> groupRsList = new ArrayList<>();
        List<List<Integer>> groupItems = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            groupItems.add(new ArrayList<>());
            groupRsList.add(new LinkedHashSet<>());
        }
        for (int i = 0; i < n; i++) {
            groupItems.get(group[i]).add(i);
        }
        //下一个组
        List<Set<Integer>> groupNextList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            groupNextList.add(new HashSet<>());
        }
        //下一个任务
        List<Set<Integer>> itemNextList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            itemNextList.add(new HashSet<>());
        }
        //任务入度
        int[] itemIn = new int[n];
        for (int i = 0; i < beforeItems.size(); i++) {
            List<Integer> beforeItem = beforeItems.get(i);
            itemIn[i] = beforeItem.size();
            for (Integer item : beforeItem) {
                itemNextList.get(item).add(i);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        int handleItemCount=0;
        for (int i = 0; i < n; i++) {
            if (itemIn[i] == 0) {
                queue.add(i);
                handleItemCount++;
            }

        }
        //组入度
        int[] groupIn = new int[m];
        Set<Integer> nextQueue = new HashSet<>();

        while (!queue.isEmpty()) {
            int item = queue.poll();
            groupRsList.get(group[item]).add(item);
            Set<Integer> nextList = itemNextList.get(item);
            for (Integer nextItem : nextList) {
                itemIn[nextItem]--;
                if (itemIn[nextItem] < 0) {
                    return new int[0];
                }
                if (group[nextItem] != group[item]) {
                    if(!groupNextList.get(group[item]).contains(group[nextItem])){
                        groupNextList.get(group[item]).add(group[nextItem]);
                        groupIn[group[nextItem]]++;
                    }

                }
                if (itemIn[nextItem] == 0) {
                    handleItemCount++;
                    nextQueue.add(nextItem);
                }

            }
            if (queue.isEmpty()) {
                queue.addAll(nextQueue);
                nextQueue.clear();
            }

        }

        if(handleItemCount<n){
            return new int[0];
        }

        int handleGroupCount=0;
        List<Integer> itemRsList  = new ArrayList<>();
        List<Integer> rsList  = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if(groupIn[i]==0){
                handleGroupCount++;
                rsList.add(i);
                itemRsList.addAll(groupRsList.get(i));
                queue.add(i);
            }
        }

        while (!queue.isEmpty()){
            int groupId=queue.poll();
            Set<Integer> nextList=groupNextList.get(groupId);
            for(Integer nextGroupId:nextList){
                groupIn[nextGroupId]--;
                if(groupIn[nextGroupId]<0){
                    return new int[0];
                }
                if(groupIn[nextGroupId]==0){
                    handleGroupCount++;
                    nextQueue.add(nextGroupId);
                    rsList.add(nextGroupId);
                    itemRsList.addAll(groupRsList.get(nextGroupId));
                }
            }
            if (queue.isEmpty()) {
                queue.addAll(nextQueue);
                nextQueue.clear();
            }

        }
        if(handleGroupCount<m){
            return new int[0];
        }
        int[] rs = new int[n];
        for (int i = 0; i < itemRsList.size(); i++) {
            rs[i]=itemRsList.get(i);
        }
        return rs;
    }
}

复杂度分析

令 n 为数组长度。

laofuWF commented 3 years ago
class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for(int i = 0; i < n; i++){
            if(group[i] == -1) {
                group[i] = m++;
            }
        }

        int[] countsGroup = new int[m];
        List<List<Integer>> graphGroups = buildGraphGroups(group, beforeItems, countsGroup, m, n);

        int[] countsItem = new int[n];
        List<List<Integer>> graphItems = buildGraphItems(beforeItems, countsItem, n);

        // to acquire the topologically sorted groups and items
        List<Integer> groupsSorted = topologicalSort(graphGroups, countsGroup);
        List<Integer> itemsSorted = topologicalSort(graphItems, countsItem);
        // to detect any cycle
        if(groupsSorted.isEmpty() || itemsSorted.isEmpty()) return new int[0];

        // to build up the relationship between sorted groups and sorted items
        List<List<Integer>> groupsToItems = new ArrayList<List<Integer>>(m);
        for(int i = 0; i < m; i++){
            groupsToItems.add(new ArrayList<Integer>());
        }
        for(int item : itemsSorted){
            groupsToItems.get(group[item]).add(item);
        }

        // to generate the answer array
        int[] ans = new int[n];
        int idx = 0;
        // to first pick, in front groups, front elements/items 
        for(int curGroup : groupsSorted){
            for(int item : groupsToItems.get(curGroup)) {
                ans[idx++] = item;
            }
        }

        return ans;
    }

    private List<Integer> topologicalSort(List<List<Integer>> graph, int[] counts){
        final int N = counts.length;
        List<Integer> res = new ArrayList<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < N; i++){
            if(counts[i] == 0){
                queue.add(i);
            }
        }

        int count = 0;
        while(!queue.isEmpty()){
            int node = queue.poll();
            res.add(node); 
            count++;
            for(int neighbor : graph.get(node)){
                if(--counts[neighbor] == 0){
                    queue.offer(neighbor);
                }
            }
        }

        return count == N ? res : new ArrayList<Integer>();
    }

    private List<List<Integer>> buildGraphItems(List<List<Integer>> beforeItems, 
                                                int[] counts, 
                                                int n){
        List<List<Integer>> graph = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++){
            graph.add(new ArrayList<Integer>());
        }

        for(int i = 0; i < n; i++){
            List<Integer> items = beforeItems.get(i);
            for(int item : items){
                graph.get(item).add(i);
                ++counts[i];
            }
        }

        return graph;
    }

    private List<List<Integer>> buildGraphGroups(int[] group, 
                                                 List<List<Integer>> beforeItems, 
                                                 int[] counts, 
                                                 int m,
                                                 int n){
        List<List<Integer>> graph = new ArrayList<List<Integer>>(m);
        for(int i = 0; i < m; i++){
            graph.add(new ArrayList<Integer>());
        }

        for(int i = 0; i < n; i++){
            int toGroup = group[i];
            List<Integer> fromItems = beforeItems.get(i);
            for(int fromItem : fromItems){
                int fromGroup = group[fromItem];
                if(fromGroup != toGroup){
                    graph.get(fromGroup).add(toGroup);
                    ++counts[toGroup];
                }
            }
        }

        return graph;
    }
}
yanjyumoso commented 3 years ago
class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

        # DAG
        def topological(items, indegree, neighbors):
            q = collections.deque([])
            res = []
            for i in items:
                if not indegree[i]:
                    q.append(i)
            while q:
                cur = q.popleft()
                res.append(cur)

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

            return res

        max_gid = m

        for project in range(n):
            if group[project] == -1:
                group[project] = max_gid
                max_gid += 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 before in beforeItems[project]:
                # group graph
                if group[before] != group[project]:
                    group_indegree[group[project]] += 1
                    group_neighbors[group[before]].append(group[project])
                # project graph
                else:
                    project_indegree[project] += 1
                    project_neighbors[before].append(project)

        ans = []

        group_queue = topological([i for i in range(max_gid)], group_indegree, group_neighbors)

        if len(group_queue) != max_gid:
            return []

        for gid in group_queue:
            project_queue = topological(group_projects[gid], project_indegree, project_neighbors)

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

        return ans
zol013 commented 3 years ago

拓扑排序 BFS Python 3 Code

class Soution:
def sortItems(self, n, m, group, beforeItems):
    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
Menglin-l commented 3 years ago

思路:

确认过是自己不会的题。。。学习了题解做法,根据beforeItems可以得到项目item的拓扑排序结果,由数组group可以得到项目item对应的组的编号。


代码部分:

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

        // 根据项目的拓扑排序结果,项目到组的多对一关系,建立组到项目的一对多关系
        // key:组,value:在同一组的项目列表
        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(V + E)

Space: O(V + E)

kidexp commented 3 years ago

thoughts

参考的官方题解 因为我们要group 同一个group的project在一起 所以我们要建立group的dep

所以先建group 和 project 的graph,再拓扑排序 group first ,然后对于每个group内部的project 再进行一个拓扑排序

code

from collections import deque, defaultdict

def topological_sort(node_list, in_degree_dict, graph):
    result = []
    queue = deque()
    for node in node_list:
        if in_degree_dict[node] == 0:
            queue.append(node)
    while queue:
        node = queue.pop()
        result.append(node)
        for next_node in graph[node]:
            in_degree_dict[next_node] -= 1
            if in_degree_dict[next_node] == 0:
                queue.appendleft(next_node)
    return result

class Solution:
    def sortItems(
        self, n: int, m: int, group: List[int], beforeItems: List[List[int]]
    ) -> List[int]:
        # assign unique group id for project without a group
        max_project = m
        for i in range(len(group)):
            if group[i] == -1:
                group[i] = max_project
                max_project += 1
        distinct_group_list = list(set(group))
        # build group and project graph
        group_in_degree = defaultdict(int)
        group_graph = defaultdict(list)
        project_in_degree = defaultdict(int)
        project_graph = defaultdict(list)
        group_project_dict = defaultdict(list)
        for i in range(len(beforeItems)):
            group_project_dict[group[i]].append(i)
            for dep in beforeItems[i]:

                if group[i] != group[dep]:
                    group_in_degree[group[i]] += 1
                    group_graph[group[dep]].append(group[i])
                else:
                    project_in_degree[i] += 1
                    project_graph[dep].append(i)
        # sort the group first
        sorted_group = topological_sort(
            distinct_group_list, group_in_degree, group_graph
        )
        if len(sorted_group) != len(distinct_group_list):
            return []

        result = []
        # sort project in each group
        for i in sorted_group:
            sorted_projects = topological_sort(
                group_project_dict[i], project_in_degree, project_graph
            )
            if len(sorted_projects) != len(group_project_dict[i]):
                return []
            result.extend(sorted_projects)

        return result

complexity

m 是图里面边的个数, n是图里面node 的个数

时间 O(m+n)

空间 O(m+n)

yingliucreates commented 3 years ago

link:

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

这题我连题目都没看懂。我再回头来看。 >_<

代码 Javascript

const sortItems = function (n, m, group, beforeItems) {
  const vertexs = new Map();
  const groupVertexs = new Map();
  let groupNo = m;
  for (let i = 0; i < n; i++) {
    vertexs.set(i, {
      neighbors: new Set(),
      indegree: 0,
    });
    if (group[i] === -1) {
      group[i] = groupNo++;
    }
    if (!groupVertexs.has(group[i])) {
      groupVertexs.set(group[i], {
        v: new Set(),
        neighbors: new Set(),
        indegree: 0,
      });
    }
    groupVertexs.get(group[i]).v.add(i);
  }

  for (let i = 0; i < n; i++) {
    for (const before of beforeItems[i]) {
      if (!vertexs.get(before).neighbors.has(i)) {
        vertexs.get(i).indegree += 1;
      }
      vertexs.get(before).neighbors.add(i);

      const groupOfBefore = group[before];
      if (groupOfBefore === group[i]) continue;
      if (!groupVertexs.get(groupOfBefore).neighbors.has(group[i])) {
        groupVertexs.get(group[i]).indegree += 1;
      }
      groupVertexs.get(groupOfBefore).neighbors.add(group[i]);
    }
  }

  const zeroGroup = [];
  for (const group of groupVertexs) {
    if (group[1].indegree === 0) {
      zeroGroup.push(group[0]);
    }
  }
  const result = [];
  let cntGroup = 0;
  let cntV = 0;
  const groupTotal = groupVertexs.size;

  while (zeroGroup.length) {
    const top = zeroGroup.pop();
    cntGroup += 1;
    const v = groupVertexs.get(top).v;
    const total = v.size;
    const zero = [];

    for (const i of v) {
      if (vertexs.get(i).indegree === 0) {
        zero.push(i);
      }
    }
    while (zero.length) {
      const it = zero.pop();
      result.push(it);
      for (const n of vertexs.get(it).neighbors) {
        vertexs.get(n).indegree -= 1;
        if (v.has(n) && vertexs.get(n).indegree === 0) {
          zero.push(n);
        }
      }
    }
    if (result.length - cntV !== total) {
      return [];
    }
    cntV = result.length;

    for (const groupneigbor of groupVertexs.get(top).neighbors) {
      groupVertexs.get(groupneigbor).indegree -= 1;
      if (groupVertexs.get(groupneigbor).indegree === 0) {
        zeroGroup.push(groupneigbor);
      }
    }
  }
  return cntGroup === groupTotal ? result : [];
};
ZacheryCao commented 3 years ago

Solution

Topological sorting. Topologically sort items and groups. Assign sorted item to its corresponding group. Based on the group order to append it's items. For each project without group, assign it to a new different group.

Code (python)

import collections
class Solution:
    def sortItems(self, n, m, group, beforeItems):
        for u in range(len(group)):
            if group[u] == -1:
                group[u] = m
                m+=1
        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  
        item_order = self.get_top_order(graph_items, indegree_items)
        group_order = self.get_top_order(graph_groups, indegree_groups)
        if not item_order or not group_order: return []

        order_within_group = collections.defaultdict(list)
        for v in item_order:
            order_within_group[group[v]].append(v)

        res = []
        for group in group_order:
            res += order_within_group[group]
        return res

    def get_top_order(self, 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 []

Complexity:

Time: O(V+E) Space: O(V+E)

Daniel-Zheng commented 3 years ago

思路

拓扑排序。

代码(C++)

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

复杂度分析

ghost commented 3 years ago

题目

  1. Sort Items by Groups Respecting Dependencies

思路

不会做 抄的标答

代码


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

        for i in range(n):
            if group[i] == -1:
                group[i] = max_id
                max_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 i in range(n):
            group_projects[group[i]].append(i)

            for pre in beforeItems[i]:
                if group[pre] != group[i]:
                    group_indegree[group[i]] += 1
                    group_neighbors[group[pre]].append(group[i])
                else:
                    project_indegree[i]+=1
                    project_neighbors[pre].append(i)

        res = []

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

        if len(group_queue) != max_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):
        res = []
        queue = collections.deque([])

        for item in items:
            if indegree[item] == 0:
                queue.append(item)

        while(queue):
            t = queue.popleft()
            res.append(t)

            for neighbor in neighbors[t]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return res

复杂度

Space: O(V+E) Time: O(V+E)

biscuit279 commented 3 years ago

思路 :没思路

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]
        """
        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

    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

时间复杂度:O(V+E) 空间复杂度:O(V+E)

wenlong201807 commented 3 years ago

代码块

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) => {
  // 拓扑排序:id列表,图,入度
  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 : [];
};

时间复杂度和空间复杂度

V-Enzo commented 3 years ago

思路:

先打上卡,还没有很明白,晚点来仔仔细细再捋一下。

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

Complexity:

Time:O(n) Space:O(n)

wangyifan2018 commented 3 years ago

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    groups, inDegrees := make([][]int, n+m), make([]int, n+m)
    for i, g := range group {
        if g > -1 {
            g += n
            groups[g] = append(groups[g], i)
            inDegrees[i]++
        }
    }
    for i, ancestors := range beforeItems {
        gi := group[i]
        if gi == -1 {
            gi = i
        } else {
            gi += n
        }
        for _, ancestor := range ancestors {
            ga := group[ancestor]
            if ga == -1 {
                ga = ancestor
            } else {
                ga += n
            }
            if gi == ga {
                groups[ancestor] = append(groups[ancestor], i)
                inDegrees[i]++
            } else {
                groups[ga] = append(groups[ga], gi)
                inDegrees[gi]++
            }
        }
    }
    res := []int{}
    for i, d := range inDegrees {
        if d == 0 {
            sortItemsDFS(i, n, &res, &inDegrees, &groups)
        }
    }
    if len(res) != n {
        return nil
    }
    return res
}

func sortItemsDFS(i, n int, res, inDegrees *[]int, groups *[][]int) {
    if i < n {
        *res = append(*res, i)
    }
    (*inDegrees)[i] = -1
    for _, ch := range (*groups)[i] {
        if (*inDegrees)[ch]--; (*inDegrees)[ch] == 0 {
            sortItemsDFS(ch, n, res, inDegrees, groups)
        }
    }
}
···
chaggle commented 3 years ago

title: "Day 31 1203. 项目管理" date: 2021-10-10T10:30:34+08:00 tags: ["Leetcode", "c++", "graph"] categories: ["91-day-algorithm"] draft: true


1203. 项目管理

题目

有 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] 不含重复元素

题目思路

  • 1、拓扑排序类问题,今日问题较难,使用单拓扑排序可能不太行,所以尝试使用双拓扑排序的思路!由于这几天生病,只能CV一下,过几天后再来补一道解析!
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {     
        vector<int> ans, blank;
        //如果某个项目不属于当前任何小组,新建一个小组,并且把它分给这个小组,为了避免冲突,新的小组编号从m开始
        for(int i = 0; i < group.size(); i++)
        if(group[i] == -1)
        {
            group[i] = m++;
        }

        //分别保存组间依赖关系、项目之间的依赖关系、各个小组负责的项目
        vector<int> topoGroup[m], topoItem[n], groupItem[m];
        //分别保存小组和项目在图中的入度
        int groupDgr[m], itemDgr[n];
        //避免添加多余的有向边,依赖关系只需要一条有向边就可以表示
        unordered_set<int> vis;
        memset(groupDgr, 0, sizeof groupDgr);
        memset(itemDgr, 0 ,sizeof itemDgr);
        for(int i = 0; i < beforeItems.size(); i++)
        {
            //将项目添加到对应的组内
            groupItem[group[i]].push_back(i);
            for(int j = 0; j < beforeItems[i].size(); j++)
            {
                //hashval用于判断是否有重复的邮箱边出现
                int u = beforeItems[i][j], hashval = group[u] * m + group[i];
                topoItem[u].push_back(i);
                itemDgr[i]++;
                //自己不能依赖自己
                if(group[i] == group[u] || vis.find(hashval) != vis.end()) continue;
                vis.insert(hashval);
                topoGroup[group[u]].push_back(group[i]);
                groupDgr[group[i]]++;
            }
        }

        //groupOrder保存了组的顺序
        vector<int> groupOrder;
        queue<int> q;
        for(int i = 0; i < m; i++)
        if(groupDgr[i] == 0) q.push(i);

        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            groupOrder.push_back(u);
            for(int i = 0; i < topoGroup[u].size(); i++)
            {
                int v = topoGroup[u][i];
                groupDgr[v]--;
                if(groupDgr[v] == 0) q.push(v);
            }
        }

        //判断组内项目是否满足拓扑排序
        for(int i = 0; i < groupOrder.size(); i++)
        {
            int t = groupOrder[i];
            for(int j = 0; j < groupItem[t].size(); j++)
            {
                int u = groupItem[t][j];
                if(itemDgr[u] == 0) q.push(u);
            }

            int cnt = 0;
            while(!q.empty())
            {
                int u = q.front();
                q.pop();
                cnt++;
                ans.push_back(u);
                for(int j = 0; j < topoItem[u].size(); j++)
                {
                    int v = topoItem[u][j];
                    itemDgr[v]--;
                    if(itemDgr[v] == 0 && group[v] == t) q.push(v);
                }
            }
            if(cnt != groupItem[t].size()) return blank;
        }

        //如果组间关系不能满足拓扑排序,必定有项目不能加入ans内
        if(ans.size() != n) return blank;

        return ans;
    }
};

复杂度

qyw-wqy commented 3 years ago
class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        Map<Integer, Integer> groupIndegree = new HashMap<>(); // <GroupId: Indegree of groupId>
        Map<Integer, Integer> memberIndegree = new HashMap<>(); /// <MemberId: Indegree of memberId>
        Map<Integer, List<Integer>> groupMember = new HashMap<>(); // <GroupId: List of memberIds in the group>
        Map<Integer, Set<Integer>> groupGraph = new HashMap<>(); // <GroupId: List of groupIds that have to go after>
        Map<Integer, List<Integer>> memberGraph = new HashMap<>(); // <MemberId: List of memberIds that have to go after>

        // if a group is -1 change it to -i-1;
        for (int i = 0; i < n; i++) {
            if (group[i] < 0) {
                group[i] = - i - 1;
            }
            groupIndegree.put(group[i], 0);
            groupGraph.putIfAbsent(group[i], new HashSet<>());
            groupMember.putIfAbsent(group[i], new ArrayList<>());
            groupMember.get(group[i]).add(i);
        }

        for (int i = 0; i < n; i++) {
            memberGraph.putIfAbsent(i, new ArrayList<>());
            memberIndegree.put(i, beforeItems.get(i).size());
            for (int before : beforeItems.get(i)) {
                memberGraph.putIfAbsent(before, new ArrayList<>());    
                memberGraph.get(before).add(i);
                if (group[before] != group[i] && groupGraph.get(group[before]).add(group[i])) {
                    groupIndegree.put(group[i], groupIndegree.get(group[i]) + 1);
                }
            }
        }

        // topological sort on the group first. 
        Deque<Integer> groupQ = new ArrayDeque<>();
        Deque<Integer> memberQ = new ArrayDeque<>();

        for (int g : groupIndegree.keySet()) {
            if (groupIndegree.get(g) == 0) groupQ.addLast(g);
        }

        int[] res = new int[n];
        int k = 0;

        while (!groupQ.isEmpty()) {
            int curGroup = groupQ.removeFirst();

             // For each group, topological sort the members in the group.
            for (int member : groupMember.get(curGroup)) {
                if (memberIndegree.get(member) == 0) {
                    memberQ.add(member);
                }
            }
            int count = 0;
            while (!memberQ.isEmpty()) {
                int member = memberQ.removeFirst();
                res[k++] = member;
                count++;
                for (int nextMember : memberGraph.get(member)) {
                    memberIndegree.put(nextMember, memberIndegree.get(nextMember) - 1);
                    if (group[nextMember] == g && memberIndegree.get(nextMember) == 0) {
                        memberQ.addLast(nextMember);
                    }
                }
            }
            if (count < groupMember.get(curGroup).size()) break;

            for (int nextGroup : groupGraph.get(curGroup)) {
                groupIndegree.put(nextGroup, groupIndegree.get(nextGroup) - 1);
                if (groupIndegree.get(nextGroup) == 0) groupQ.addLast(nextGroup);
            }
        }

        if (k < n) return new int[0];
        return res;
    }
}

Time: O(M+N) Space: O(M+N)

sxr000511 commented 3 years ago

class Solution { public: vector sortItems(int n, int m, vector& group, vector<vector>& beforeItems) {
vector ans, blank; //如果某个项目不属于当前任何小组,新建一个小组,并且把它分给这个小组,为了避免冲突,新的小组编号从m开始 for(int i = 0; i < group.size(); i++) if(group[i] == -1) { group[i] = m++; }

    //分别保存组间依赖关系、项目之间的依赖关系、各个小组负责的项目
    vector<int> topoGroup[m], topoItem[n], groupItem[m];
    //分别保存小组和项目在图中的入度
    int groupDgr[m], itemDgr[n];
    //避免添加多余的有向边,依赖关系只需要一条有向边就可以表示
    unordered_set<int> vis;
    memset(groupDgr, 0, sizeof groupDgr);
    memset(itemDgr, 0 ,sizeof itemDgr);
    for(int i = 0; i < beforeItems.size(); i++)
    {
        //将项目添加到对应的组内
        groupItem[group[i]].push_back(i);
        for(int j = 0; j < beforeItems[i].size(); j++)
        {
            //hashval用于判断是否有重复的邮箱边出现
            int u = beforeItems[i][j], hashval = group[u] * m + group[i];
            topoItem[u].push_back(i);
            itemDgr[i]++;
            //自己不能依赖自己
            if(group[i] == group[u] || vis.find(hashval) != vis.end()) continue;
            vis.insert(hashval);
            topoGroup[group[u]].push_back(group[i]);
            groupDgr[group[i]]++;
        }
    }

    //groupOrder保存了组的顺序
    vector<int> groupOrder;
    queue<int> q;
    for(int i = 0; i < m; i++)
    if(groupDgr[i] == 0) q.push(i);

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        groupOrder.push_back(u);
        for(int i = 0; i < topoGroup[u].size(); i++)
        {
            int v = topoGroup[u][i];
            groupDgr[v]--;
            if(groupDgr[v] == 0) q.push(v);
        }
    }

    //判断组内项目是否满足拓扑排序
    for(int i = 0; i < groupOrder.size(); i++)
    {
        int t = groupOrder[i];
        for(int j = 0; j < groupItem[t].size(); j++)
        {
            int u = groupItem[t][j];
            if(itemDgr[u] == 0) q.push(u);
        }

        int cnt = 0;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            cnt++;
            ans.push_back(u);
            for(int j = 0; j < topoItem[u].size(); j++)
            {
                int v = topoItem[u][j];
                itemDgr[v]--;
                if(itemDgr[v] == 0 && group[v] == t) q.push(v);
            }
        }
        if(cnt != groupItem[t].size()) return blank;
    }

    //如果组间关系不能满足拓扑排序,必定有项目不能加入ans内
    if(ans.size() != n) return blank;

    return ans;
}

};

zszs97 commented 3 years ago

开始刷题

题目简介

【Day 31 】2021-10-10 - 1203. 项目管理

题目思路

题目代码

代码块

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

复杂度

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

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

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

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

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

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

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

完全不懂,抄的答案。晚点慢慢再仔细分析。

mmboxmm commented 3 years ago

思路

  1. build item graph
  2. build group graph
  3. top sort item graph
  4. break it to each group's top sort results
  5. top sort group graph
  6. output result based on group top sort order

代码

fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
  var ng = m
  val groups = group.mapIndexed { i, g -> if (g == -1) ng++ else g }

  val igraph = Array<MutableSet<Int>>(n) { mutableSetOf() }
  val ggraph = Array<MutableSet<Int>>(ng) { mutableSetOf() }

  for (i in 0 until n) {
    for (b in beforeItems[i]) {
      val ig = groups[i]
      val bg = groups[b]
      if (ig == bg) {
        igraph[b].add(i)
      } else {
        ggraph[bg].add(ig)
      }
    }
  }

  fun inDegree(graph: Array<MutableSet<Int>>): IntArray {
    val res = IntArray(graph.size) { 0 }

    for (es in graph) {
      for (e in es) {
        res[e]++
      }
    }
    return res
  }

  fun topSort(graph: Array<MutableSet<Int>>): List<Int> {
    val ins = inDegree(graph)
    val queue = mutableListOf<Int>()
    for ((i, d) in ins.withIndex()) {
      if (d == 0) queue.add(i)
    }
    val res = mutableListOf<Int>()

    while (queue.isNotEmpty()) {
      val top = queue.removeAt(0)
      res.add(top)

      for (next in graph[top]) {
        ins[next]--
        if (ins[next] == 0) queue.add(next)
      }
    }
    return res
  }

  val itop = topSort(igraph)
  if (itop.size != igraph.size) return intArrayOf()
  val tops = Array<MutableList<Int>>(ng) { mutableListOf() }
  for (i in itop) {
    tops[groups[i]].add(i)
  }

  val gtop = topSort(ggraph)
  if (gtop.size != ggraph.size) return intArrayOf()

  val res = mutableListOf<Int>()
  for (g in gtop) {
    res.addAll(tops[g])
  }
  return res.toIntArray()
}
tongxw commented 3 years ago

思路

这题不会,写个210凑数

代码

class Solution {;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // establish a course DAG
        List<Integer>[] dag = new List[numCourses];
        int[] inDegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            // edge[1] -> edge[0]
            if (dag[edge[1]] == null) {
                dag[edge[1]] = new ArrayList<>();
            }
            dag[edge[1]].add(edge[0]);
            inDegree[edge[0]] += 1;
        }

        // top-sort bfs
        // List<Integer> ans = new ArrayList<>();
        // bfs(ans, dag, inDegree);
        // return ans.size() == numCourses ? ans.stream().mapToInt(Integer::intValue).toArray() : new int[0];

        // top sort dfs
        int[] visited = new int[numCourses]; // 0 - not visited, 1 - visiting, 2 - visited
        // boolean hasCircle = false;
        Deque<Integer> stack = new LinkedList<>();
        for (int i=0; i<numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(i, dag, visited, stack)) {
                    return new int[0];
                }
            }
        }

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

    private void bfs(List<Integer> ans, List<Integer>[] dag, int[] inDegree) {
        Queue<Integer> q = new LinkedList<>();
        for (int i=0; i<dag.length; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            int course = q.poll();
            ans.add(course);
            if (dag[course] != null) {
                for (int next : dag[course]) {
                    inDegree[next] -= 1;
                    if (inDegree[next] == 0) {
                        q.offer(next);
                    }
                }
            }
        }
    }

    private boolean dfs(int course, List<Integer>[] dag, int[] visited, Deque<Integer> stack) {
        visited[course] = 1;
        if (dag[course] != null) {
            for (int next : dag[course]) {
                if (visited[next] == 0) {
                    if (!dfs(next, dag, visited, stack)) {
                        return false;
                    }
                } else if (visited[next] == 1) {
                    // circle
                    return false;
                } else {
                    // no op for visited == 2
                }
            }
        }
        visited[course] = 2;
        stack.push(course);
        return true;
    }
}

TC: O(v+e) SC: O(v+e)

st2yang commented 3 years ago

思路

代码

复杂度

ymkymk commented 3 years ago

思路

参考官网

代码

``

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;
        // 给未分配的 item 分配一个 groupId
        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),其中 n 为点数,m 为边数

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

nerrolk commented 3 years ago

打卡

shixinlovey1314 commented 3 years ago

Title:1203. Sort Items by Groups Respecting Dependencies

Question Reference LeetCode

Solution

Topology sort. Note: that if item a is in group 1, item b is in group 2, and item a needs to happen before item b, then group 1 needs to happen before group2.

Note:

  1. When calculating the indegrees, be care for not to count the same edge twice, otherwise there won't be a topology sort.
  2. When an item's group id is -1, that means it can be for any group, thus for each of the group -1, we should assign it an unique group id rather than put them into a same group, otherwise, we will fail if two gourp -1 items are on the oppsite side of another group.

Code

class Solution {
public:
    vector<int> topologySort(set<int>& items, vector<int>& indegrees, map<int, set<int>>& relation) {
        queue<int> proQ;
        vector<int> ans;

        for (int v : items)
            if (indegrees[v] == 0) {
                proQ.push(v);
            }

        while (!proQ.empty()) {
            int i = proQ.front();
            proQ.pop();

            ans.push_back(i);

            for (int v : relation[i]) {
                if (--indegrees[v] == 0)
                    proQ.push(v);
            }
        }

        return ans;
    }

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        map<int, set<int>> group2item;
        vector<int> itmeIndegrees(n,0);
        map<int, set<int>> groupRelation;
        map<int, set<int>> itemRelation;
        set<int> groupIds;
        vector<int> ans;
        int groupIDMax = m;

        for (int i = 0; i < group.size(); i++) {
            if (group[i] == -1)
                group[i] = groupIDMax++;

            group2item[group[i]].insert(i);
            groupIds.insert(group[i]);
        }

        vector<int> groupIndegrees(groupIDMax,0);

        for (int i = 0; i < beforeItems.size(); i++) {
            for (int j : beforeItems[i]) {
                // In the same group, order items.
                if (group[i] == group[j]) {
                    if (!itemRelation[j].count(i)) {
                        itmeIndegrees[i]++;
                        itemRelation[j].insert(i);
                    }
                } else {
                // In different group, order groups
                    if (!groupRelation[group[j]].count(group[i])) {
                        groupIndegrees[group[i]]++;
                        groupRelation[group[j]].insert(group[i]);
                    } 
                }
            }
        }

        vector<int> groupOrder = topologySort(groupIds, groupIndegrees, groupRelation);

        if (groupOrder.size() != groupIds.size())
            return vector<int>();

        for (int v : groupOrder) {
            vector<int> tmpOrder = topologySort(group2item[v], itmeIndegrees, itemRelation);
            if (tmpOrder.size() != group2item[v].size())
                return vector<int>();

            for (int x : tmpOrder)
                ans.push_back(x);
        }

        return ans;
    }
};

Complexity

Time Complexity and Explanation

O(v + e)

Space Complexity and Explanation

O(v + e)

EggEggLiu commented 3 years ago

思路

BFS + 拓扑排序

代码

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

复杂度

时间 O(m+n)

空间 O(m+n)

zhiyuanpeng commented 3 years ago
class Solution:
    def topologicalSort(self, vertices, edges):
        """
        vertices: list of any type
        edges: list of list of two indices of vertices
        """
        n = len(vertices)
        out_edges = [[] for _ in range(n)]
        in_deg = [0 for _ in range(n)]
        for i, j in edges:
            out_edges[i].append(j)
            in_deg[j] += 1

        inds = [i for i in range(n) if in_deg[i] == 0]
        for i in inds:
            for j in out_edges[i]:
                in_deg[j] -= 1
                if in_deg[j] == 0:
                    inds.append(j)
        if len(inds) == n:
            return [vertices[i] for i in inds]
        else:
            raise RuntimeError # there is a loop

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        groups = [[] for _ in range(m)] # items in each group
        intra_lookup = [{} for _ in range(m)] # indices of items in each group
        for i in range(n):
            if group[i] == -1: # create new group for items belonging to no group
                intra_lookup.append({i: 0}) # one item in such group
                groups.append([i])
            else:
                g = group[i]
                intra_lookup[g][i] = len(groups[g])
                groups[g].append(i)
        # remove empty groups
        intra_lookup = [g for i, g in enumerate(intra_lookup) if groups[i]]
        groups = [g for g in groups if g]
        m = len(groups)

        inter_lookup = [None for _ in range(n)] # group each item belongs to
        for g, ita in enumerate(intra_lookup):
            for i in ita:
                inter_lookup[i] = g

        # beforeItems are splited into two
        inter_b, intra_b = [], [[]for _ in range(m)]
        for i, b in enumerate(beforeItems):
            gi = inter_lookup[i]
            for j in b:
                gj = inter_lookup[j]
                if gi == gj:
                    # edge inside one group
                    intra_b[gi].append(
                        [intra_lookup[gi][j], intra_lookup[gi][i]])
                else:
                    # edge between groups
                    inter_b.append([gj, gi])

        try:
            # sort groups
            groups = self.topologicalSort(list(zip(groups, intra_b)),
                                            inter_b)
            # sort items inside each group
            for g in range(m):
                groups[g] = self.topologicalSort(groups[g][0], groups[g][1])
            return sum(groups, [])
        except RuntimeError:
            return []
RocJeMaintiendrai commented 3 years ago

题目

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) {
        Map<Integer, List<Integer>> gGraph = new HashMap<>();
        Map<Integer, List<Integer>> iGraph = new HashMap<>();
        for(int i = 0; i < group.length; i++) {
            if(group[i] == -1) group[i] = m++;
        }

        int[] itemInDegree = new int[n];
        int[] groupInDegree = new int[m];

        for(int to = 0; to < beforeItems.size(); to++) {
            int toGroup = group[to];
            for(int from : beforeItems.get(to)) {
                itemInDegree[to]++;
                if(!iGraph.containsKey(from)) {
                    iGraph.put(from, new ArrayList<Integer>());
                }
                iGraph.get(from).add(to);
            }
        }

        //build item graph
        for(int to = 0; to < group.length; to++) {
            int toGroup = group[to];
            for(int from : beforeItems.get(to)) {
                int fromGroup = group[from];
                if(gGraph.containsKey(fromGroup)) {
                    gGraph.put(fromGroup, new ArrayList<Integer>());
                }
                if(fromGroup != toGroup) {
                    groupInDegree[toGroup]++;
                    gGraph.get(fromGroup).add(toGroup);
                }
            }
        }

        List<Integer> iList = tpSort(iGraph, itemInDegree, n);
        List<Integer> gList = tpSort(gGraph, groupInDegree, m);

        if(iList.size() == 0 || gList.size() == 0) return new int[0];

        Map<Integer, List<Integer>> groupedList = new HashMap<>();
        for(int item : iList) {
            int grp = group[item];
            if(!groupedList.containsKey(grp)) {
                groupedList.put(grp, new ArrayList<Integer>());
            }
            groupedList.get(grp).add(item);
        }

        int i = 0;
        int[] ans = new int[n];
        for(int grp : gList) {
            if(!groupedList.containsKey(grp)) continue;
            for(int item : groupedList.get(grp)) {
                ans[i] = item;
                i++;
            }
        }
        return ans;
    }

    public List<Integer> tpSort(Map<Integer, List<Integer>> graph, int[] inDegree, int count) {
        List<Integer> ans = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < inDegree.length; i++) {
            if(inDegree[i] == 0) q.offer(i);
        }
        while(!q.isEmpty()) {
            int cur = q.poll();
            ans.add(cur);
            if(!graph.containsKey(cur)) continue;
            for(int next : graph.get(cur)) {
                inDegree[next]--;
                if(inDegree[next] == 0) q.offer(next);
            }
        }
        return count == ans.size() ? ans : new ArrayList<>();
    }
}

复杂度分析

时间复杂度

O(V + E)

空间复杂度

O(V + E)

biancaone commented 3 years ago
class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        def makeGraphs():
            items = collections.defaultdict(dict)
            groups = {}
            for i, g in enumerate(group):
                items[g][i] = set()
                if g not in groups:
                    groups[g] = set()

            for i, ancestors in enumerate(beforeItems):
                for anc in ancestors:
                    if group[i] != group[anc]:
                        groups[group[anc]].add(group[i])
                    else:
                        items[group[i]][anc].add(i)
            return items, groups

        items, groups = makeGraphs()

        def sortGraph(G, stack):
            visiting = set() 
            visited = set()
            def dfs(node):
                if node in visiting: return False
                if node in visited: return True

                visiting.add(node)
                visited.add(node)
                for child in G[node]:
                    if not dfs(child):
                        return False
                stack.append(node)
                visiting.remove(node)
                return True

            for node in G:
                if not dfs(node):
                    return [] 
            return stack

        groupsStack = []
        sortGraph(groups, groupsStack)
        if not groupsStack: 
            return []

        res = []
        for g in reversed(groupsStack):
            groupItems = []
            sortGraph(items[g], groupItems)
            if not groupItems: 
                return []
            res.extend(reversed(groupItems))
        return res
Laurence-try commented 3 years ago

思路

官方题解

代码

使用语言:Python3

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 + E), N is number of node, E is number of edge 空间复杂度:O(N + E)

ai2095 commented 3 years ago

LC1203. Sort Items by Groups Respecting Dependencies

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

Topics

Similar Questions

Hard

Medium

思路

This is a topological sorting problem. Firstly sort the groups, then sort the items in each group.

代码 Python

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

复杂度分析

时间复杂度: O(V+E)
空间复杂度:O(V+E)

leolisgit commented 3 years ago

思路

参考了一些解法。两次拓扑排序。因为item之间的依赖关系,导致了组与组之间也有了先后顺序。

  1. 分别对group和item进行拓扑排序
  2. 对于没有分组的item,这里使用一个技巧,每个item单独一个组。最后输出的是item,组号并不影响。

代码

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

        List<Integer>[] groupGraph = new ArrayList[m];
        List<Integer>[] itemGraph = new ArrayList[n];

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

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

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

        // construct adjecent graph of groups and items
        for (int i = 0; i < n; i++) {
            int groupId = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroupId = group[beforeItem];
                if (beforeGroupId != groupId) {
                    groupGraph[beforeGroupId].add(groupId);
                    groupIndegree[groupId]++;
                } else {
                    itemGraph[beforeItem].add(i);
                    itemIndegree[i]++;
                }
            }
        }

        List<Integer> groupList = topSort(groupGraph, groupIndegree, m);
        List<Integer> itemList = topSort(itemGraph, itemIndegree, n);

        if (groupList.size() == 0 || itemList.size() == 0) {
            return new int[0];
        }

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

        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupList) {
            List<Integer> items = map.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }

        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    public List<Integer> topSort(List<Integer>[] graph, int[] indegree, int n) {
        List<Integer> ret = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            Integer u = q.poll();
            ret.add(u);
            for (Integer v : graph[u]) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    q.offer(v);
                }
            }
        }

        return ret.size() == n ? ret : new ArrayList<>();
    }
}

复杂度

时间:O(v + e)
空间:O(v + e)

simonsayshi commented 3 years ago
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        unordered_map<int, vector<int>> groupGraph;
        unordered_map<int, int> groupIndegree;

        vector<vector<int>> groupItems(m, vector<int>());

        for(int i = 0; i < n;i++) {
            if(group[i] != -1) {
                groupItems[group[i]].push_back(i);
            } else {
                group[i] = groupItems.size();
                groupItems.push_back(vector<int>{i});
            }
        }

        for(int j = 0; j < groupItems.size(); j++) {
            groupIndegree[j] = 0;
        }

        for(int i = 0; i < n ;i++) {
            for(const int beforeItem : beforeItems[i]) {
                int groupId = group[i];
                if(groupId != group[beforeItem]) {

                    groupGraph[group[beforeItem]].push_back(groupId);
                    groupIndegree[groupId]++;
                }
            }
        }

        vector<int> sortedGroup = graphSort(groupGraph, groupIndegree);
        vector<int> res;
        if (sortedGroup.size() < groupItems.size()) return res;

        for(const int&i : sortedGroup) {
            vector<int> curOrder = itemsSort(groupItems[i], beforeItems,group);
            if(curOrder.size() < groupItems[i].size())
                return vector<int>();
            for(auto j: curOrder)
                res.push_back(j);
        }

        return res;

    }

    vector<int> itemsSort(vector<int>&items , vector<vector<int>>& beforeItems, vector<int>& group) {
        unordered_map<int, vector<int>> itemsGraph;
        unordered_map<int, int> itemsIndegree;

        for(auto item : items) {
            itemsIndegree[item] = 0;
           for(const int beforeItem:beforeItems[item]) {
               if(group[item] == group[beforeItem]) {
                    itemsGraph[beforeItem].push_back(item);
                    itemsIndegree[item]++;
               }

           }
        }
        vector<int> res = graphSort(itemsGraph, itemsIndegree);
        return res;
    }

    vector<int> graphSort(unordered_map<int, vector<int>> &edge, unordered_map<int, int>& indegree) {
        queue<int> q;
        vector<int> res;

        for(auto a:indegree) {
            if(a.second == 0)
                q.push(a.first);
        }

        while(!q.empty()) {
            int temp = q.front();
            q.pop();
            res.push_back(temp);
            for(auto b : edge[temp]) {
                indegree[b]--;
                if(indegree[b] == 0)
                    q.push(b);
            }
        }
        return res;
    }
};
QiZhongdd commented 3 years ago
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
JK1452470209 commented 3 years ago

思路

太难了,抄一下答案

代码

class Solution {
       public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        //不属于任何组的任务指派个独立组id
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        List<Set<Integer>> groupRsList = new ArrayList<>();
        List<List<Integer>> groupItems = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            groupItems.add(new ArrayList<>());
            groupRsList.add(new LinkedHashSet<>());
        }
        for (int i = 0; i < n; i++) {
            groupItems.get(group[i]).add(i);
        }
        //下一个组
        List<Set<Integer>> groupNextList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            groupNextList.add(new HashSet<>());
        }
        //下一个任务
        List<Set<Integer>> itemNextList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            itemNextList.add(new HashSet<>());
        }
        //任务入度
        int[] itemIn = new int[n];
        for (int i = 0; i < beforeItems.size(); i++) {
            List<Integer> beforeItem = beforeItems.get(i);
            itemIn[i] = beforeItem.size();
            for (Integer item : beforeItem) {
                itemNextList.get(item).add(i);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        int handleItemCount=0;
        for (int i = 0; i < n; i++) {
            if (itemIn[i] == 0) {
                queue.add(i);
                handleItemCount++;
            }

        }
        //组入度
        int[] groupIn = new int[m];
        Set<Integer> nextQueue = new HashSet<>();

        while (!queue.isEmpty()) {
            int item = queue.poll();
            groupRsList.get(group[item]).add(item);
            Set<Integer> nextList = itemNextList.get(item);
            for (Integer nextItem : nextList) {
                itemIn[nextItem]--;
                if (itemIn[nextItem] < 0) {
                    return new int[0];
                }
                if (group[nextItem] != group[item]) {
                    if(!groupNextList.get(group[item]).contains(group[nextItem])){
                        groupNextList.get(group[item]).add(group[nextItem]);
                        groupIn[group[nextItem]]++;
                    }

                }
                if (itemIn[nextItem] == 0) {
                    handleItemCount++;
                    nextQueue.add(nextItem);
                }

            }
            if (queue.isEmpty()) {
                queue.addAll(nextQueue);
                nextQueue.clear();
            }

        }

        if(handleItemCount<n){
            return new int[0];
        }

        int handleGroupCount=0;
        List<Integer> itemRsList  = new ArrayList<>();
        List<Integer> rsList  = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if(groupIn[i]==0){
                handleGroupCount++;
                rsList.add(i);
                itemRsList.addAll(groupRsList.get(i));
                queue.add(i);
            }
        }

        while (!queue.isEmpty()){
            int groupId=queue.poll();
            Set<Integer> nextList=groupNextList.get(groupId);
            for(Integer nextGroupId:nextList){
                groupIn[nextGroupId]--;
                if(groupIn[nextGroupId]<0){
                    return new int[0];
                }
                if(groupIn[nextGroupId]==0){
                    handleGroupCount++;
                    nextQueue.add(nextGroupId);
                    rsList.add(nextGroupId);
                    itemRsList.addAll(groupRsList.get(nextGroupId));
                }
            }
            if (queue.isEmpty()) {
                queue.addAll(nextQueue);
                nextQueue.clear();
            }

        }
        if(handleGroupCount<m){
            return new int[0];
        }
        int[] rs = new int[n];
        for (int i = 0; i < itemRsList.size(); i++) {
            rs[i]=itemRsList.get(i);
        }
        return rs;
    }
}

复杂度

时间复杂度:O(N)

空间复杂度:O(N)

shamworld commented 3 years ago

代码

var sortItems = function(n, m, group, beforeItems) {
     const groupItems = new Array(m + n).fill(0).map(() => []);
    // 将未分组自身为一组
    let k = m;
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            group[i] = k++;
        }
        groupItems[group[i]].push(i);
    }
    // 组间关系及入度
    const groupGraph = new Array(m + n).fill(0).map(() => []);
    const groupIn = new Array(m + n).fill(0);
    // 组内关系及入度
    const itemGraph = new Array(n).fill(0).map(() => []);
    const itemIn = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        const curGroupId = group[i];
        for (let beforeIndex of beforeItems[i]) {
            const beforeGroupId = group[beforeIndex];
            if (curGroupId === beforeGroupId) {
                // 组相同,加入组内元素关系及入度
                itemIn[i] += 1;
                itemGraph[beforeIndex].push(i);
            } else {
                // 如果组间关系存在,不重复保存
                if (groupGraph[beforeGroupId].indexOf(curGroupId) >= 0) continue;
                groupIn[curGroupId] += 1;
                groupGraph[beforeGroupId].push(curGroupId);
            }
        }
    }

    /**
     * @param {number[][]} graph 关联关系
     * @param {number[]} inNum 入度
     * @param {number[]} groupItems 组元素或同组内元素
     * @return {number[]}
     */
    const topSort = (graph, inNum, groupItems) => {
        const queue = [];
        // 入度为0的加入队列
        for (let inIndex of groupItems) {
            if (inNum[inIndex] === 0) {
                queue.push(inIndex);
            }
        }
        const temp = [];
        while (queue.length) {
            // 取队首元素
            const index = queue.shift();
            temp.push(index);
            for (let i = 0; i < graph[index].length; i++) {
                // 指向元素的下标
                const inIndex = graph[index][i];
                // 入度减1
                inNum[inIndex] -= 1;
                // 当入度为0时,也加入到队列
                if (inNum[inIndex] === 0) {
                    queue.push(inIndex)
                }
            }
        }
        return temp.length === groupItems.length ? temp : [];
    }
    // 表示所有组
    const groupIds = new Array(m + n).fill(0).map((item, index) => index);
    const groupTopSort = topSort(groupGraph, groupIn, groupIds);
    if (groupTopSort.length === 0) {
        return [];
    }
    let res = [];
    for (let groupId of groupTopSort) {
        const curGroup = groupItems[groupId];
        // 组内可能没有分配任务
        if (curGroup.length === 0) {
            continue;
        }
        if (curGroup.length === 1) {
            // 长度为1,未分组元素,组内无需排序
            res.push(curGroup[0]);
        } else {
            // 长度大于1,组内进行排序
            const itemTopSort = topSort(itemGraph, itemIn, curGroup);
            if (itemTopSort.length === 0) {
                return [];
            }
            res = [...res, ...itemTopSort];
        }
    }
    return res
};
florenzliu commented 3 years ago

Explanation

Python

class class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
       def topSort(deg, graph):
            stack = [v for v in range(len(graph)) if deg[v] == 0]
            res = []
            while stack:
                curr = stack.pop()
                res.append(curr)
                for v in graph[curr]:
                    deg[v] -= 1
                    if deg[v] == 0:
                        stack.append(v)
            return res if len(res) == len(graph) else []

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

        groupGraph = [[] for _ in range(m)]
        itemGraph = [[] for _ in range(n)]
        groupDegree = [0] * m
        itemDegree = [0] * n

        for i in range(n):
            for item in beforeItems[i]:
                itemGraph[item].append(i)
                itemDegree[i] += 1
                if group[item] != group[i]:
                    groupDegree[group[i]] += 1
                    groupGraph[group[item]].append(group[i])

        groupTopSort = topSort(groupDegree, groupGraph)
        itemTopSort = topSort(itemDegree, itemGraph)

        if not groupTopSort or not itemTopSort:
            return []

        orderInGroup = defaultdict(list)
        for i in itemTopSort:
            orderInGroup[group[i]].append(i)

        ans = []
        for j in groupTopSort:
            ans += orderInGroup[j]

        return ans

Complexity:

carsonlin9996 commented 3 years ago

两次拓扑排序

  1. group的构图和入度
  2. items的构图和入度
  3. 建立group -> 多个items的映射
  4. 根据group的拓扑排序加入 group对应的items入结果

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

        Map<Integer, List<Integer>> groupNeighbor = new HashMap<>();
        Map<Integer, List<Integer>> itemsNeighbor = new HashMap<>();
        //初始化
        for (int i = 0; i < m; i++) {
            groupNeighbor.put(i, new ArrayList<Integer>());
        }
        for (int i = 0; i < n; i++) {
            itemsNeighbor.put(i, new ArrayList<Integer>());
        }

        //构图
        int[] groupIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        for (int i = 0; i < group.length; i++) {
            int curGrp = group[i];

            for (int beforeItem : beforeItems.get(i)) {
                int beforeGrp = group[beforeItem];

                if (beforeGrp != curGrp) {
                    groupNeighbor.get(beforeGrp).add(curGrp);
                    groupIndegree[curGrp]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int beforeItem : beforeItems.get(i)) {
                itemsNeighbor.get(beforeItem).add(i);
                itemsIndegree[i]++;

            }
        }

        //topo sort
        List<Integer> groupSort = topoSort(groupIndegree, groupNeighbor, m);

        if (groupSort.size() == 0) {
            return new int[0];
        }

        List<Integer> itemsSort = topoSort(itemsIndegree, itemsNeighbor, n);
        if (itemsSort.size() == 0) {
            return new int[0];
        }

        Map<Integer, List<Integer>> groupItemMap = new HashMap<>();
        //用哈希表建立group 对应多个items的映射
        for (int item : itemsSort) {
            if (!groupItemMap.containsKey(group[item])) {
                groupItemMap.put(group[item], new ArrayList<>());
            }
            groupItemMap.get(group[item]).add(item);
        }

        List<Integer> res = new ArrayList<>();
        //根据group的topo排序依次加入group -> items的映射
        for (Integer grp : groupSort) {
            List<Integer> temp = groupItemMap.getOrDefault(grp, new ArrayList<>());

            res.addAll(temp);
        }
        //list 转成 int[]
        return res.stream().mapToInt(Integer::valueOf).toArray(); 
    }

    private List<Integer> topoSort(int[] indegreeCnt, Map<Integer, List<Integer>> neighbors, int n) {
        List<Integer> res = new ArrayList<>();

        Queue<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            if (indegreeCnt[i] == 0) {
                queue.offer(i);
                res.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (int neighbor : neighbors.get(cur)) {
                indegreeCnt[neighbor] = indegreeCnt[neighbor] - 1;

                if (indegreeCnt[neighbor] == 0) {
                    queue.offer(neighbor);
                    res.add(neighbor);
                }

            }
        }    
        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}
ginnydyy commented 3 years ago

Problem

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

Notes

Solution

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // preprocessing - assign new group id to the -1th groups
        for(int i = 0; i < n; i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }

        // build the group and item adjacent lists and indegree arrays
        // to make sure all the groups and items have corresponding list in the map, initiate with empty list first
        Map<Integer, List<Integer>> groupAdjacentList = new HashMap<>();
        for(int i = 0; i < m; i++){
            groupAdjacentList.put(i, new ArrayList<>());
        }
        Map<Integer, List<Integer>> itemAdjacentList = new HashMap<>();
        for(int i = 0; i < n; i++){
            itemAdjacentList.put(i, new ArrayList<>());
        }
        int[] groupIndegree = new int[m];
        int[] itemIndegree = new int[n];

        for(int i = 0; i < n; i++){ // iterate all the items and build the adjacent list and indegree array
            int currentGroup = group[i];
            for(int dependentItem: beforeItems.get(i)){
                // item
                itemAdjacentList.get(dependentItem).add(i);
                itemIndegree[i]++;

                // group
                int dependentGroup = group[dependentItem];
                if(dependentGroup != currentGroup){ // avoid putting duplicate groups in the adjacent list
                    groupAdjacentList.get(dependentGroup).add(currentGroup);
                    groupIndegree[currentGroup]++;
                }
            }
        }

        // sort the groups and items in topo order
        // if the groups or items cannot be sorted in topological order, then no solution, return empty array
        List<Integer> groupTopoList = topoSort(groupAdjacentList, groupIndegree);
        if(groupTopoList.size() == 0){
            return new int[0];
        }

        List<Integer> itemTopoList = topoSort(itemAdjacentList, itemIndegree);
        if(itemTopoList.size() == 0){
            return new int[0];
        }

        // group the items in topo order as per their groups
        Map<Integer, List<Integer>> groupMap = new HashMap<>();
        for(int i = 0; i < n; i++){
            int item = itemTopoList.get(i);
            int groupId = group[item];
            if(!groupMap.containsKey(groupId)){
                groupMap.put(groupId, new ArrayList<>());
            }
            groupMap.get(groupId).add(item);
        }

        // As per group topo order, put the items in each group to the result array
        int[] result = new int[n];
        int index = 0;
        for(int i = 0; i < m; i++){
            int groupId = groupTopoList.get(i);
            if(!groupMap.containsKey(groupId)){
                continue;
            }
            for(int item: groupMap.get(groupId)){
                result[index] = item;
                index++;
            }
        }

        return result;
    }

    private List<Integer> topoSort(Map<Integer, List<Integer>> adjacentList, int[] indegree){
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()){
            int item = queue.poll();
            result.add(item);
            for(int nextItem: adjacentList.get(item)){
                indegree[nextItem]--;
                if(indegree[nextItem] == 0){
                    queue.offer(nextItem);
                }
            }
        }

        // if result size doesn't equal to the number of items
        // it means the items cannot be sorted in topo order
        if(result.size() != indegree.length){
            return new ArrayList<>();
        }

        return result;
    }
}

Complexity

chang-you commented 3 years ago

Official Java Solution

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

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

        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<>();
    }
}
septasset commented 3 years ago

太难了,官方解也看得很吃力

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

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

        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<>();
    }
}
15691894985 commented 3 years ago

【day 31】1203. 项目管理

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

思路:关键点:

yan0327 commented 3 years ago

mark一下,今天状态不好,看不动,回头再看

type Node struct{
    preCount int
    NextIDs []int
}

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    groupItems := make([][]int, m+n)
    maxGroupID := m-1
    for i:=0;i<n;i++{
        if group[i] == -1{
            maxGroupID++
            group[i] = maxGroupID
        }
        groupItems[group[i]] = append(groupItems[group[i]], i)
    }

    gItem := make([]Node, n)
    for i:=0; i < n;i++{
        for _, preID := range beforeItems[i]{
            gItem[i].preCount++
            gItem[preID].NextIDs = append(gItem[preID].NextIDs, i)
        }
    }

    gGroup := make([]Node, maxGroupID+1)
    for i:=0; i<n; i++{
        curID := group[i]
        for _,preID := range beforeItems[i]{
            preID := group[preID]
            if curID == preID{
                continue
            }
            gGroup[curID].preCount++
            gGroup[preID].NextIDs = append(gGroup[preID].NextIDs, curID)
        }
    }

    q := make([]int, 0)
    for i,v := range gGroup{
        if v.preCount == 0{
            q = append(q,i)
        }
    }
    retGroup := make([]int, 0)
    for len(q) > 0{
        k := len(q)
        for k>0{
            k--
            curID := q[0]
            q = q[1:]
            retGroup = append(retGroup,curID)
            for _,NextID := range gGroup[curID].NextIDs{
                gGroup[NextID].preCount--
                if gGroup[NextID].preCount == 0{
                    q = append(q,NextID)
                }
            }
        }
    }
    if len(retGroup) != maxGroupID+1{
        return []int{}
    }
    ret := make([]int, 0)
    for j:=0; j <= maxGroupID; j++{
        q = make([]int,0)
        for _,id := range groupItems[retGroup[j]]{
            if gItem[id].preCount == 0{
                q = append(q,id)
            }
        }
        for len(q) > 0{
            k := len(q)
            for k > 0{
                k--
                curID := q[0]
                q = q[1:]
                ret = append(ret, curID)
                for _,nextID := range gItem[curID].NextIDs{
                    gItem[nextID].preCount--
                    if gItem[nextID].preCount== 0 && group[nextID]==retGroup[j]{
                        q = append(q, nextID)
                    }
                }
            }
        }
    }
    if len(ret) != n {
        return []int{}
    }
    return ret
}