华为OD题目： 快速开租建站

华为OD题目： 快速开租建站

知识点 BFSQ搜索拓扑排序
时间限制: 1s 空间限制: 256MB 限定语言: 不限
题目描述:
当前IT部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套IT服务。
每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为1。部署任务项之间可能存在依赖，假如任务2依赖任务1，
那么等任务1部署完，任务2才能部署。任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。
没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。
给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。

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

输出描述:
个整数，表示一个站点的最短开站时间
补充说明:
1<taskNum<=100
1=<relationsNum<=5000

示例1
输入:
5
5
0 4
1 2
1 3
2 3
2 4
输出:
3

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

示例2
输入:
5
3
0 3
0 4
1 3

输出:
2

解题思路：

• 可以用深度优先的方式来做，本题可以理解为取所有任务里，启动时间最长的一个
• for循环的时候，依次取getMinNeedTime（taskNum）,取其中最大的一个
• 在 getMinNeedTime（taskNum）方法中，会对当前（taskNum）所依赖的递归调用此方法，
• 为了避免重复递归，用一个taskMinTimes数组保存每个任务的最小启动时间

public class My {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int taskNum = Integer.parseInt(sc.nextLine());
        int relationsNum = Integer.parseInt(sc.nextLine());

        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < relationsNum; i++) {
            String line = sc.nextLine();
            String[] strings = line.split(" ");
            int left = Integer.parseInt(strings[0]);
            int right = Integer.parseInt(strings[1]);
            List<Integer> list = map.getOrDefault(left, new ArrayList<>());
            list.add(right);
            map.put(left, list);
        }
        int[] taskMinTimes = new int[taskNum];

        int res = 0;
        for (int i = 0; i < taskNum; i++) {
            int needTime = getMinNeedTime(i, map, taskMinTimes);
            res = Math.max(res, needTime);
        }
        System.out.println(res);
    }

    //获取当前任务启动所需时间，就是所有依赖的任务里面时间最多的一个，为了减枝，用一个数组记录任务的最小启动时间
    public static int getMinNeedTime(int currNum, Map<Integer, List<Integer>> map, int[] taskMinTimes) {
        List<Integer> list = map.getOrDefault(currNum, new ArrayList<>());
        if (list.size() == 0) {
            //记录当前task任务所需的时间
            taskMinTimes[currNum] = 1;
            return 1;
        }

        int minDependTime = Integer.MIN_VALUE;
        for (int taskNum : list) {
            //先看看任务数组有没有值，如果数组里还没记录最小启动时间，那么递归获取,否则，如果已经有了，直接进行下面的比较
            if (taskMinTimes[taskNum] == 0) {
                taskMinTimes[taskNum] = getMinNeedTime(taskNum, map, taskMinTimes);
            }
            minDependTime = Math.max(minDependTime, taskMinTimes[taskNum]);
        }
        int needTime = minDependTime + 1;
        //记录当前task任务所需的时间
        taskMinTimes[currNum] = needTime;
        return needTime;

    }

}