华为OD机试 - 任务最优调度 - 深度优先搜索dfs算法（Java 2023 B卷 200分）

在这里插入图片描述

- 专栏导读
- 一、题目描述
- 二、输入描述
- 三、输出描述
- - 1、输入
  - 2、输出
  - 3、说明
- 四、解题思路
- - 1、题目解读
  - 2、解题思路
  - 3、具体步骤
- 五、Java算法源码
- 六、效果展示
- - 1、输入
  - 2、输出
  - 3、说明
  - - 思路分析
    - 执行顺序

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定一个正整数数组表示待系统执行的任务列表，数组的每一个元素代表一个任务，元素的值表示该任务的类型。

请计算执行完所有任务所需的最短时间。

任务执行规则如下

任务可以按任意顺序执行，且每个任务执行耗时间均为1个时间单位；
两个同类型的任务之间必须有长度为N个单位的冷却时间，比如N为2时，在时间K执行了类型3的任务，那么K+1和K+2两个时间不能执行类型3任务；
系统在任何一个单位时间内都可以执行一个任务，或者等待状态。

说明：数组最大长度为1000，速度最大值1000。

二、输入描述

第一行记录一个用半角逗号分隔的数组，数组长度不超过1000，数组元素的值不超过1000。第二行记录任务冷却时间，N为正整数，N<=100。

三、输出描述

输出为执行完所有任务所需的最短时间。

1、输入

2,2,2,3
2

2、输出

3、说明

时间1：执行任务2
时间2：执行任务3，因为冷却时间为2，所以时间2不能执行任务2
时间3：系统等待，因为冷却时间为2，所以时间3不能执行任务1和任务2
时间4：执行任务2
时间5：系统等待
时间6：系统等待
时间7：执行任务2

四、解题思路

1、题目解读

每个任务执行耗时间均为1个时间单位
两个同类型的任务之间必须有长度为N个单位的冷却时间
输出为执行完所有任务所需的最短时间。

2、解题思路

因为任务有冷却时间，为了缩短冷却时间，任务数量多的应该先执行。

3、具体步骤

第一行输入若干个任务；
定义任务编号与数量关系的Map（key：任务编号，value：任务数量,冷却时间，并进行数据初始化；
冷却时间说明：
- 未执行的任务，默认-1；
- 执行的任务，默认为coolingTime；
- 每执行一个任务，-1；
第二行输入冷却时间coolingTime；
定义加入执行的任务列表builder；
通过深度优先搜索dfs进行任务最优调度；
- 如果任务列表为空，则停止搜索；
- 获取优先执行的任务，任务优先执行的条件：（①为了缩短冷却时间，任务数量多的应该先执行；②不处于冷却时间内）；
  - 定义满足条件的待执行任务maxTask；
  - 遍历map，获取任务数量和任务冷却时间；
  - 如果任务数量最多 and 不处于冷却时间内，获取优先执行的任务；
  - 处于冷却时间内的任务，冷却时间-1；
  - 返回优先执行的任务编号；
如果获取到了优先执行的任务编号；
- 将该任务的数量-1；
- 冷却时间置为coolingTime；
- 如果任务数量-1后，等于0，表示该任务执行完毕，从map中移除；
将优先执行的任务编号加入builder，如果没有获取到可以优先执行的任务，将默认值“wait”加入到builder，表示占位；
最后输出为执行完所有任务所需的最短时间。

五、Java算法源码

public class OdTest02 {
    static int coolingTime = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 若干个任务
        String[] taskArr = sc.nextLine().split(",");
        /**
         * key：任务编号
         * value：任务数量,冷却时间
         * 冷却时间说明：
         * 未执行的任务，默认-1
         * 执行的任务，默认为coolingTime
         * 每执行一个任务，-1
         */
        Map<String, String> map = new HashMap<>();
        for (int i = 0; i < taskArr.length; i++) {
            String task = taskArr[i];
            Integer sum = 0;
            if (map.containsKey(task)) {
                sum = Integer.valueOf(map.get(task).split(",")[0]);
            }
            sum++;
            map.put(task, sum+","+(-1));
        }

        // 冷却时间
        coolingTime = Integer.valueOf(sc.nextLine());

        // 搜索任务数量最多 且不处于冷却时间的任务 去执行
        dfs(map);

        System.out.println(builder.deleteCharAt(builder.length()-1));
        System.out.println(builder.toString().split(",").length);
    }

    // 加入执行的任务列表
    static StringBuilder builder = new StringBuilder();

    /**
     * 搜索任务数量最多 且不处于冷却时间的任务 去执行
     */
    private static void dfs(Map<String, String> map) {
        // 如果任务列表为空，则停止搜索
        if(map.size() == 0){
            return;
        }

        String maxTask = getMaxTask(map);
        if(!maxTask.equals("wait")){
            String value = map.get(maxTask);
            int sum = Integer.valueOf(value.split(",")[0]);
            sum--;
            if(sum > 0){
                map.put(maxTask,sum + "," + coolingTime);
            }else{
                map.remove(maxTask);
            }
        }

        builder.append(maxTask).append(",");
        // 搜索任务数量最多 且不处于冷却时间的任务 去执行
        dfs(map);
    }

    /**
     * 任务执行的条件：
     * 1. 为了缩短冷却时间，任务数量多的应该先执行
     * 2. 不处于冷却时间内
     */
    private static String getMaxTask(Map<String, String> map) {
        // 满足条件的待执行任务
        String maxTask = "wait";
        Integer maxValue = -1;
        for (Map.Entry<String,String> entry : map.entrySet()) {
            // 任务数量
            int sum = Integer.valueOf(entry.getValue().split(",")[0]);
            // 任务冷却时间
            int cool = Integer.valueOf(entry.getValue().split(",")[1]);
            // 任务数量最多 and 不处于冷却时间内
            if (sum > maxValue && cool<=0) {
                maxTask = entry.getKey();
                maxValue = sum;
            }

            // 处于冷却时间内的任务，冷却时间-1
            if(cool > 0){
                cool--;
                map.put(entry.getKey(),sum + "," + cool);
            }
        }
        return maxTask;
    }
}