博客
关于我
leetcode 1203.项目管理(C/C++/java/python)
阅读量:224 次
发布时间:2019-03-01

本文共 10927 字,大约阅读时间需要 36 分钟。

PS:算法并非原创,仅作个人学习记录使用,侵删

题目描述

在这里插入图片描述

算法分析

一开始看到这类项目时间安排的题目,我就想起来算法里面的贪心算法。但是仔细想想,贪心算法涉及到具体的时间,且项目之间没有依赖关系。而这里的项目之间存在明显的依赖关系,于是我又想起了拓扑排序,也就是将项目作为结点,依赖关系作为边,建立有向图,然后根据有向图得出拓扑排序的序列。如果图中出现环,则说明排序无解。

代码实现

【C】

/*算法思想:拓扑排序*/int* topSort(int* returnSize, int* deg, int** graph, int* graphColSize, int* items, int itemsSize) {   //返回数组大小:returnSize,项目的承办组:deg,图的邻接矩阵:graph,图的每行大小:graphColSize,项目数组:items,项目数目:itemsSize    *returnSize = 0;//返回数组大小一开始为0    int Q[itemsSize];    int left = 0, right = 0;    for (int i = 0; i < itemsSize; i++) {   //遍历项目        if (deg[items[i]] == 0) {   //如果项目无人接管。            Q[right++] = items[i];        }    }    int* res = malloc(sizeof(int) * itemsSize);    while (left < right) {           int u = Q[left++];        res[(*returnSize)++] = u;        for (int i = 0; i < graphColSize[u]; i++) {               int v = graph[u][i];            if (--deg[v] == 0) {                   Q[right++] = v;            }        }    }    if (*returnSize == itemsSize) {           return res;    }    *returnSize = 0;    return NULL;}int* sortItems(int n, int m, int* group, int groupSize, int** beforeItems, int beforeItemsSize, int* beforeItemsColSize, int* returnSize) {       int* groupItem[n + m];    int groupItemColSize[n + m];    int groupItemColCapacity[n + m];    for (int i = 0; i < n + m; i++) {           groupItem[i] = malloc(sizeof(int));        groupItemColSize[i] = 0;        groupItemColCapacity[i] = 0;    }    // 组间和组内依赖图    int* groupGraph[n + m];    int groupGraphColSize[n + m];    int groupGraphColCapacity[n + m];    for (int i = 0; i < n + m; i++) {           groupGraph[i] = malloc(sizeof(int));        groupGraphColSize[i] = 0;        groupGraphColCapacity[i] = 0;    }    int* itemGraph[n];    int itemGraphColSize[n];    int itemGraphColCapacity[n];    for (int i = 0; i < n; i++) {           itemGraph[i] = malloc(sizeof(int));        itemGraphColSize[i] = 0;        itemGraphColCapacity[i] = 0;    }    // 组间和组内入度数组    int groupDegree[n + m];    memset(groupDegree, 0, sizeof(groupDegree));    int itemDegree[n];    memset(itemDegree, 0, sizeof(itemDegree));    int id[n + m];    for (int i = 0; i < n + m; ++i) {           id[i] = i;    }    int leftId = m;    // 给未分配的 item 分配一个 groupId    for (int i = 0; i < n; ++i) {           if (group[i] == -1) {               group[i] = leftId++;        }        if (groupItemColSize[group[i]] == groupItemColCapacity[group[i]]) {               int* x = &groupItemColCapacity[group[i]];            *x = (*x) ? (*x) * 2 : 1;            groupItem[group[i]] = realloc(groupItem[group[i]], sizeof(int) * (*x));        }        groupItem[group[i]][groupItemColSize[group[i]]++] = i;    }    // 依赖关系建图    for (int i = 0; i < n; ++i) {           int curGroupId = group[i];        for (int j = 0; j < beforeItemsColSize[i]; j++) {               int item = beforeItems[i][j];            int beforeGroupId = group[item];            if (beforeGroupId == curGroupId) {                   itemDegree[i]++;                if (itemGraphColSize[item] == itemGraphColCapacity[item]) {                       int* x = &itemGraphColCapacity[item];                    (*x) = (*x) ? (*x) * 2 : 1;                    itemGraph[item] = realloc(itemGraph[item], sizeof(int) * (*x));                }                itemGraph[item][itemGraphColSize[item]++] = i;            } else {                   groupDegree[curGroupId]++;                if (groupGraphColSize[beforeGroupId] == groupGraphColCapacity[beforeGroupId]) {                       int* x = &groupGraphColCapacity[beforeGroupId];                    (*x) = (*x) ? (*x) * 2 : 1;                    groupGraph[beforeGroupId] = realloc(groupGraph[beforeGroupId], sizeof(int) * (*x));                }                groupGraph[beforeGroupId][groupGraphColSize[beforeGroupId]++] = curGroupId;            }        }    }    // 组间拓扑关系排序    int groupTopSortSize;    int* groupTopSort = topSort(&groupTopSortSize, groupDegree, groupGraph, groupGraphColSize, id, n + m);    if (groupTopSortSize == 0) {           *returnSize = 0;        return NULL;    }    int* ans = malloc(sizeof(int) * groupTopSortSize);    *returnSize = 0;    // 组内拓扑关系排序    for (int i = 0; i < groupTopSortSize; i++) {           int curGroupId = groupTopSort[i];        int size = groupItemColSize[curGroupId];        if (size == 0) {               continue;        }        int resSize;        int* res = topSort(&resSize, itemDegree, itemGraph, itemGraphColSize, groupItem[curGroupId], groupItemColSize[curGroupId]);        if (resSize == 0) {               *returnSize = 0;            return NULL;        }        for (int j = 0; j < resSize; j++) {               ans[(*returnSize)++] = res[j];        }    }    return ans;}

【C++】

/*算法思想:拓扑排序*/class Solution {   public:    vector
sortItems(int n, int m, vector
& group, vector
>& beforeItems) { for(int i = 0; i < n; i++){ //遍历项目 if(group[i] == -1) group[i] = m++;//无人接管的分配一个虚拟团队号 } vector
> itemgraph(n); vector
> groupgraph(m); vector
itemIndegree(n, 0); vector
groupIndegree(m, 0); for(int i = 0; i < n; i++){ for(auto j : beforeItems[i]){ itemgraph[j].push_back(i);//建图 itemIndegree[i]++;//记录出入度 if(group[i] != group[j]){ // 注意条件 // 团队也建图,记录出入度 groupgraph[group[j]].push_back(group[i]); groupIndegree[group[i]]++; } } } vector
> g_items(m); // item 拓扑排序 queue
q; for(int i = 0; i < n; i++) if(itemIndegree[i] == 0) q.push(i); int countItem = 0; while(!q.empty()){ int i = q.front(); q.pop(); countItem++; g_items[group[i]].push_back(i); //每个item顺序存入自己的团队 for(auto j : itemgraph[i]){ if(--itemIndegree[j]==0) q.push(j); } } if(countItem != n) return { }; // 团队拓扑排序 vector
g_order; for(int i = 0; i < m; i++) if(groupIndegree[i] == 0) q.push(i); int countgroup = 0; while(!q.empty()){ int g = q.front(); q.pop(); countgroup++; g_order.push_back(g); for(auto j : groupgraph[g]){ if(--groupIndegree[j]==0) q.push(j); } } if(countgroup != m) return { }; // 写入答案 vector
ans(n); int idx = 0; for(auto g : g_order){ for(auto i : g_items[g]) ans[idx++] = i; } return ans; }};

【java】

class Solution {       public int[] sortItems(int n, int m, int[] group, List
> beforeItems) { List
> groupItem = new ArrayList
>(); for (int i = 0; i < n + m; ++i) { groupItem.add(new ArrayList
()); } // 组间和组内依赖图 List
> groupGraph = new ArrayList
>(); for (int i = 0; i < n + m; ++i) { groupGraph.add(new ArrayList
()); } List
> itemGraph = new ArrayList
>(); for (int i = 0; i < n; ++i) { itemGraph.add(new ArrayList
()); } // 组间和组内入度数组 int[] groupDegree = new int[n + m]; int[] itemDegree = new int[n]; List
id = new ArrayList
(); 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
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
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
topSort(int[] deg, List
> graph, List
items) { Queue
queue = new LinkedList
(); for (int item : items) { if (deg[item] == 0) { queue.offer(item); } } List
res = new ArrayList
(); 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
(); }}

【python】

class Solution:    def sortItems(self, n, m, group, beforeItems):        # 构建组到任务的映射        group2Items = collections.defaultdict(set)        index = m        for i in range(n):            if group[i] == -1:                group[i] = index                group2Items[index] = set([i])                index += 1            else:                group2Items[group[i]].add(i)        # 构建组的拓扑图        beforeGroupsDic, preGroupsDic = {   }, {   }        for i in range(index):            beforeGroupsDic[i] = set()            preGroupsDic[i] = set()        for i in range(n):            for j in beforeItems[i]:                beforeGroupsDic[group[i]].add(group[j])                preGroupsDic[group[j]].add(group[i])        # 去除组内部的节点 如果存在环,在任务级别判断        for i in range(index):            if i in beforeGroupsDic[i]:                beforeGroupsDic[i].remove(i)                preGroupsDic[i].remove(i)        res = []        while beforeGroupsDic:            # 找出所有入度为0的小组            groups = [key for key, values in beforeGroupsDic.items() if not beforeGroupsDic[key]]            if not groups:                return []            # 处理小组的拓扑关系            for g in groups:                beforeGroupsDic.pop(g)                for g1 in preGroupsDic[g]:                    beforeGroupsDic[g1].remove(g)                preGroupsDic.pop(g)            # 对小组内部建立拓扑图            for key in groups:                its = list(group2Items[key])                # 对这些点建立拓扑图                beforeItemsDic, preItemsDic = {   }, {   }                for i in its:                    beforeItemsDic[i] = set()                    preItemsDic[i] = set()                for i in its:                    for j in beforeItems[i]:                        if group[i] == group[j]:                            beforeItemsDic[i].add(j)                            preItemsDic[j].add(i)                while beforeItemsDic:                    items = [k for k, v in beforeItemsDic.items() if not beforeItemsDic[k]]                    if not items:                        return []                    res += items                    # 处理项目的拓扑关系                    for item in items:                        beforeItemsDic.pop(item)                        for item1 in preItemsDic[item]:                            if item1 in beforeItemsDic:                                beforeItemsDic[item1].remove(item)                        preItemsDic.pop(item)        return res

转载地址:http://aquv.baihongyu.com/

你可能感兴趣的文章
mysql 存储过程 注入_mysql 视图 事务 存储过程 SQL注入
查看>>
MySQL 存储过程参数:in、out、inout
查看>>
mysql 存储过程每隔一段时间执行一次
查看>>
mysql 存在update不存在insert
查看>>
Mysql 学习总结(86)—— Mysql 的 JSON 数据类型正确使用姿势
查看>>
Mysql 学习总结(87)—— Mysql 执行计划(Explain)再总结
查看>>
Mysql 学习总结(88)—— Mysql 官方为什么不推荐用雪花 id 和 uuid 做 MySQL 主键
查看>>
Mysql 学习总结(89)—— Mysql 库表容量统计
查看>>
mysql 实现主从复制/主从同步
查看>>
mysql 审核_审核MySQL数据库上的登录
查看>>
mysql 导入 sql 文件时 ERROR 1046 (3D000) no database selected 错误的解决
查看>>
mysql 导入导出大文件
查看>>
MySQL 导出数据
查看>>
mysql 将null转代为0
查看>>
mysql 常用
查看>>
MySQL 常用列类型
查看>>
mysql 常用命令
查看>>
Mysql 常见ALTER TABLE操作
查看>>
MySQL 常见的 9 种优化方法
查看>>
MySQL 常见的开放性问题
查看>>