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

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

专栏导读

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

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

一、题目描述

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

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

任务执行规则如下

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

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

二、输入描述

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

三、输出描述

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

1、输入

2,2,2,3
2

2、输出

7

3、说明

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

四、解题思路

1、题目解读

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

2、解题思路

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

3、具体步骤

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

五、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;
    }
}

六、效果展示

1、输入

2,2,3,2,3,3,4,4,5
3

2、输出

10

3、说明

思路分析

1. 获取每个任务编号对应的数量3个2、3个3、2个4，1个5；
2. 优先执行任务2或任务3，都可以；

执行顺序

1. 时间1：执行任务2
2. 时间2：执行任务3，因为冷却时间为3，所以时间2不能执行任务2
3. 时间3：执行任务4，因为冷却时间为3，所以时间2不能执行任务2、任务3
4. 时间4：执行任务5，因为冷却时间为3，所以时间2不能执行任务2、任务3、任务4
5. 时间5：此时还剩2个任务2、2个任务3、1个任务4，优先执行任务数量最多的，并且只有任务2不处于冷却时间内，所以执行任务2
6. 时间6：优先执行任务数量最多的，并且只有任务3不处于冷却时间内，所以执行任务3
7. 时间7：执行任务4
8. 时间8：此时只剩任务2和任务3，但都处于冷却时间，故系统等待；
9. 时间9：执行任务2
10. 时间10：执行任务3
11. 执行的任务顺序为2,3,4,5,2,3,4,wait,2,3；
12. 最后输出10

🏆下一篇：华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

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