任务最优调度

一、题目描述

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

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

任务执行规则如下:

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

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

二、输入输出描述

输入描述

• 第一行：用半角逗号分隔的数组（任务列表），数组长度 ≤ 1000，数组元素值 ≤ 1000；
• 第二行：任务冷却时间N（正整数，N ≤ 100）。

输出描述

• 一个整数，表示执行完所有任务所需的最短时间

三、示例

四、解题思路

1. 核心思想

基于任务调度的冷却约束特性，优先计算 “受冷却限制的理论最短时间”，再与 “任务总数量” 取最大值，确保既满足冷却规则，又完成所有任务。核心是 “以出现次数最多的任务为核心构建时间框架，填充其他任务或闲置，最终取约束与总量的最大值”。

2. 问题本质分析

• 表层问题：计算满足冷却约束的任务执行最短时间；
• 深层问题：

1. 约束核心：出现次数最多的任务是冷却约束的 “瓶颈”—— 这类任务的执行间隔直接决定了理论最短时间；
2. 时间框架：以最多次数任务k为基础，构建k-1个 “冷却周期”（每个周期n+1个时间单位），最后补充剩余的p个最大次数任务；
3. 边界情况：若任务种类足够多（或冷却时间为 0），冷却约束无影响，最短时间等于任务总数量；
4. 效率优化：无需模拟任务执行过程，通过数学公式直接计算，时间复杂度仅为 O (m)（m 为任务数量）。

3. 核心逻辑

• 统计基础数据：计算每个任务的出现次数，找到最大次数k和对应任务数p；
• 计算理论最短时间：(k-1)×(n+1)+p（核心任务的冷却框架时间）；
• 取最大值：理论时间与任务总数的最大值即为最终结果（保证两种场景都覆盖）。

4. 步骤拆解

1. 统计任务出现次数

   • 遍历任务列表，用HashMap记录每个任务的出现次数，得到 “任务类型 - 次数” 的映射。

2. 提取关键参数

   • 找到所有任务次数中的最大值k（出现次数最多的任务的次数）；
   • 统计有多少个任务的次数等于k，记为p。

3. 计算两种候选时间

   • 候选 1（冷却约束时间）：(k-1)×(n+1)+p；
   • 候选 2（任务总量时间）：tasks.length。

4. 确定最终结果

   • 取两个候选时间的最大值，即为满足冷却约束的最短执行时间。

五、代码实现

import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class Main { // 输入获取 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] tasks = Arrays.stream(sc.next().split(",")).mapToInt(Integer::parseInt).toArray(); int n = sc.nextInt(); System.out.println(getResult(tasks, n)); } // 算法入口 public static int getResult(int[] tasks, int n) { HashMap<Integer, Integer> cnts = new HashMap<>(); for (int task : tasks) { cnts.put(task, cnts.getOrDefault(task, 0) + 1); } // k表示:最多任务的数量 // 比如2,2,2,3， 其中任务2数量最多，有3个，则k = 3 int k = cnts.values().stream().max((a, b) -> a - b).orElse(0); // p表示:数量为k的任务个数 // 比如2,2,2,3,3,3,4， 其中数量为3的任务有2个，分别是任务2，任务3，则p=2 int p = 0; for (Integer task : cnts.keySet()) { if (cnts.get(task) == k) p++; } return Math.max((k - 1) * (n + 1) + p, tasks.length); } }