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

2023-12-14 19:38:24

在这里插入图片描述

华为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在线答疑。

在这里插入图片描述

文章来源:https://blog.csdn.net/guorui_java/article/details/135001692
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。