华为OD机试真题 Java 实现【快速开租建站】【2023Q1 200分】，附详细解题思路

一、题目描述

当前IT部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套IT服务。

每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为1。部署任务项之间可能存在依赖，假如任务2依赖任务1，那么等任务1部署完，任务2才能部署。任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。

没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。

给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。

二、输入描述

第一行是任务数taskNum,第二行是任务的依赖关系数relationsNum接下来 relationsNum 行，每行包含两个id，描述一个依赖关系，格式为: Di Dj，表示部署任务部署完成了，部署任务j才能部署，IDi 和IDj 值的范围为: [0,taskNum)注:输入保证部署任务之间的依赖不会存在环。

三、输出描述

1个整数，表示一个站点的最短开站时间。

四、解题思路

1. 创建map，用于存储任务之间的依赖关系，key为任务编号，value为依赖该任务的任务列表；
2. 循环读取num数据，将依赖关系存储map；
3. 创建一个长度为n的数组，存储每个任务的最小启动时间；
4. 创建变量time，用于记录最短开站时间；
5. 递归调用，计算任务的最小启动时间；
6. 如果当前任务没有依赖，表示该任务可以立即启动，将其最小启动时间设置为1，并返回1，停止递归；
7. 遍历当前任务依赖的任务列表，递归调用getMinTime函数来获取依赖任务的最小启动时间，取其中的最大值作为当前任务的最小启动时间minDependTime；
8. 当前任务的最小启动时间为依赖任务的最小启动时间加1，将该值记录到timeArr数组中，并返回该值；
9. 输出最短开站时间time；

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());int num = Integer.parseInt(sc.nextLine());// 1、创建map，用于存储任务之间的依赖关系，key为任务编号，value为依赖该任务的任务列表Map<Integer, List<Integer>> map = new HashMap<>();// 2、循环读取num数据，将依赖关系存储mapfor (int i = 0; i < num; i++) {String line = sc.nextLine();String[] arr = line.split(" ");int left = Integer.parseInt(arr[0]);int right = Integer.parseInt(arr[1]);List<Integer> list = map.getOrDefault(left, new ArrayList<>());list.add(right);map.put(left, list);}// 3、创建一个长度为n的数组，存储每个任务的最小启动时间int[] timeArr = new int[n];// 4、创建变量time，用于记录最短开站时间int time = 0;for (int i = 0; i < n; i++) {// 5、递归调用，计算任务的最小启动时间int needTime = getMinTime(i, map, timeArr);time = Math.max(time, needTime);}// 9、输出最短开站时间timeSystem.out.println(time);
}/**** @param index 当前位置* @param map 输入的数据集合* @param timeArr 任务时间* @return*/
public static int getMinTime(int index, Map<Integer, List<Integer>> map, int[] timeArr) {List<Integer> list = map.getOrDefault(index, new ArrayList<>());// 6、如果当前任务没有依赖，表示该任务可以立即启动，将其最小启动时间设置为1，并返回1，停止递归if (list.size() == 0) {//最小启动时间timeArr[index] = 1;return 1;}int minDependTime = Integer.MIN_VALUE;// 7、遍历当前任务依赖的任务列表，递归调用getMinTime函数来获取依赖任务的最小启动时间，// 取其中的最大值作为当前任务的最小启动时间minDependTimefor (int taskNum : list) {// 通过递归取最小启动时间if (timeArr[taskNum] == 0) {timeArr[taskNum] = getMinTime(taskNum, map, timeArr);}minDependTime = Math.max(minDependTime, timeArr[taskNum]);}// 8、当前任务的最小启动时间为依赖任务的最小启动时间加1，将该值记录到timeArr数组中，并返回该值int needTime = minDependTime + 1;timeArr[index] = needTime;return needTime;
}

六、效果展示

1、输入

5
5
0 4
1 2
1 3
2 3
2 4

2、输出

3

3、说明

有5个部署任务项，5个依赖关系，如下图所示。我们可以先同时部署任务项0和任务项1，然后部署任务项2，最后同时部署任务项3和任务项4。最短开站时间为3。

🏆下一篇：华为OD机试真题 Java 实现【获得完美走位】【2023Q1 100分】

🏆本文收录于，华为OD机试（JAVA）（2022&2023）

本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。