启动多任务排序 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。

现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。

例如: B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是:A任务，E任务，B任务，C任务，D任务。这里A和E任务都是没有依赖的，立即执行

输入描述

输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号”->”表示依赖方向。

例如A->B表示A依赖B，多个依赖之间用单个空格分割

输出描述

输出为排序后的启动任务列表，多个任务之间用单个空格分割

示例1

输入：
A->B C->B

输出：
B A C

题解

这是一个典型的拓扑排序问题，通过建立任务之间的依赖关系图，然后按照一定规则执行任务，即先执行没有依赖的任务，然后再执行依赖于前面任务的任务。

以下是解题思路和代码大致描述：

1. 使用两个字典，outdegree用于记录每个任务的出度（依赖它的任务数量），depend用于记录每个任务依赖的任务列表。
2. 遍历输入的任务依赖关系，构建任务之间的依赖图，并同时维护出度信息。
3. 利用拓扑排序的思想，循环执行以下步骤：
   • 找到出度为0的任务，如果存在多个，按字母顺序排序。
   • 将该任务加入结果集，并标记该任务已遍历。
   • 更新邻居任务的出度，将它们的出度减1。
   • 重复上述步骤，直到所有任务都被遍历。

代码使用了相应的数据结构和算法来实现这一过程，并输出最终排序后的启动任务列表。

时间复杂度：O(N + MlogM)，其中N是任务数量，M是依赖关系数量。建图和拓扑排序的过程时间复杂度为O(N + M)，排序的时间复杂度为O(MlogM)。 空间复杂度：O(N + M)，存储了任务的出度信息和依赖关系。

Java

import java.util.*;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Map<String, Integer> outdegree = new HashMap<>();
        Map<String, List<String>> depend = new HashMap<>();

        Scanner scanner = new Scanner(System.in);
        String[] relations = scanner.nextLine().split(" ");

        // 建立依赖关系，维护出度
        for (String relation : relations) {
            // a 依赖 b
            String[] parts = relation.split("->");
            String a = parts[0];
            String b = parts[1];

            depend.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
            outdegree.putIfAbsent(a, 0);
            outdegree.putIfAbsent(b, 0);
            outdegree.put(a, outdegree.get(a) + 1);
        }

        // 拓扑排序结果
        List<String> rs = new ArrayList<>();
        while (true) {
            // 找到出度为0的节点，并将其加入结果集中
            List<String> temp = new ArrayList<>();
            for (Map.Entry<String, Integer> entry : outdegree.entrySet()) {
                if (entry.getValue() == 0) {
                    temp.add(entry.getKey());
                }
            }

            // 一旦出度为0的节点不存在，则退出循环
            if (temp.isEmpty()) break;

            Collections.sort(temp);
            for (String key : temp) {
                rs.add(key);
                outdegree.put(key, -1);  // 表示已经遍历
                // 邻居节点出度 -1
                for (String neighbor : depend.getOrDefault(key, new ArrayList<>())) {
                    outdegree.put(neighbor, outdegree.get(neighbor) - 1);
                }
            }
        }

        System.out.println(String.join(" ", rs));
    }
}

Python

outdegree = dict()
depend = dict()

# 建立依赖关系，维护出度
for relation in input().split():
    # a 依赖 b
    a, b = relation.split('->')
    depend.setdefault(b, []).append(a)
    outdegree.setdefault(a, 0)
    outdegree.setdefault(b, 0)
    outdegree[a] += 1

# 拓扑排序结果
rs = []
while True:
    # 找到出度为0的节点，并将其加入结果集中
    temp = [key for key, indeg in outdegree.items() if indeg == 0]
    # 一旦出度为0的节点不存在，则退出循环
    if not temp:
        break

    temp.sort()
    for key in temp:
        rs.append(key)
        outdegree[key] = -1  # 表示已经遍历
        # 邻居节点出度 -1
        for neighbor in depend[key]:
            outdegree[neighbor] -= 1

print(" ".join(rs))

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    unordered_map<string, int> outdegree;
    unordered_map<string, vector<string>> depend;

    string relation;
    while(cin >> relation) {
        // a 依赖 b
        size_t pos = relation.find("->");
        string a = relation.substr(0, pos);
        string b = relation.substr(pos + 2);

        depend[b].emplace_back(a);
        outdegree[b];  // b 不存在时默认添加
        outdegree[a]++;
    }

    // 拓扑排序结果
    vector<string> rs;
    while (true) {
        // 找到出度为0的节点，并将其加入结果集中
        vector<string> temp;
        for (const auto& entry : outdegree) {
            if (entry.second == 0) {
                temp.push_back(entry.first);
            }
        }

        // 一旦出度为0的节点不存在，则退出循环
        if (temp.empty()) break;

        sort(temp.begin(), temp.end());
        for (const string& key : temp) {
            rs.push_back(key);
            outdegree[key] = -1;  // 表示已经遍历
            // 邻居节点出度 -1
            for (const string& neighbor : depend[key]) {
                outdegree[neighbor]--;
            }
        }
    }

    for (const string& result : rs) {
        cout << result << " ";
    }

    return 0;
}

相关练习题

题号	题目	难易
LeetCode 270	207. 课程表	中等
LeetCode 210	210. 课程表 II	中等
LeetCode 2050	2050. 并行课程 III	困难

????华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏