当前位置：首页 > article >正文

【华为OD-E卷 - 任务最优调度 100分（python、java、c++、js、c）】

article 2025/2/5 8:17:10

【华为OD-E卷 - 任务最优调度 100分（python、java、c++、js、c）】

题目

给定一个正整数数组表示待系统执行的任务列表，数组的每一个元素代表一个任务，元素的值表示该任务的类型。
请计算执行完所有任务所需的最短时间。
任务执行规则如下:
任务可以按任意顺序执行，且每个任务执行耗时间均为1个时间单位两个同类型的任务之间必须有长度为N个单位的冷却时间，比如N为2时，在时间K执行了类型3的任务，那么K+1和K+2两个时间不能执行类型3任务系统在任何一个单位时间内都可以执行一个任务，或者等待状态。说明：数组最大长度为1000，数组最大值1000

输入描述

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

输出描述

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

用例

用例一：

输入：

2,2,2,3
2

输出：

python解法

解题思路：
任务计数：

使用 Counter 来统计每个任务出现的频率，这样我们能快速了解哪些任务最多，并计算出这些任务的数量。
找到最频繁的任务：

最频繁的任务会影响到整体执行时间，因为它们需要“隔开”执行，每个相同的任务之间需要加上冷却时间。因此，我们需要计算出任务出现的最大频次以及最大频次的任务数量。
任务调度的最小时间计算：

假设最频繁的任务需要间隔 cool_down 时间来执行。如果最频繁的任务的出现次数为 max_freq，那么这类任务之间的间隔时间为 (max_freq - 1) * (cool_down + 1)，其中 (max_freq - 1) 是其他任务间隔的数量，cool_down + 1 是任务间隔时间（冷却时间加上任务本身的执行时间）。
由于可能有多个任务频率与 max_freq 相同，因此我们需要考虑最频繁的任务的数量 count_max_freq，它们会填充这些间隔位置。
最终结果：

最终的时间应该是 max((max_freq - 1) * (cool_down + 1) + count_max_freq, len(tasks))。即，如果冷却时间安排后的时间小于任务数量，那么就返回任务数量，因为每个任务至少需要执行一次

from collections import Counter

def min_exec_time(tasks, cool_down):
    # 统计每个任务的出现频率
    freq_map = Counter(tasks)
    
    # 获取任务中出现频率最高的任务次数
    max_freq = max(freq_map.values())
    
    # 计算出现最大频率的任务数量（可能有多个任务频率相同）
    count_max_freq = sum(1 for freq in freq_map.values() if freq == max_freq)
    
    # 计算调度这些任务所需的最短时间：
    # (max_freq - 1) * (cool_down + 1) 是间隔时间
    # count_max_freq 是填充这些间隔的额外任务数
    return max((max_freq - 1) * (cool_down + 1) + count_max_freq, len(tasks))

# 输入获取
input_tasks = input().split(",")  # 输入任务列表，用逗号分隔
tasks = list(map(int, input_tasks))  # 将输入转换为整数列表
cool_down = int(input())  # 输入冷却时间

# 调用函数并输出结果
print(min_exec_time(tasks, cool_down))

java解法

解题思路
任务频率统计：

使用一个 HashMap 来统计每个任务出现的频次。这样可以方便地找出任务中出现次数最多的任务，以及有多少个任务的频次相同。
计算最大频次和频次对应任务的数量：

找到出现频次最高的任务数，并计算有多少种任务的出现频率等于最大频率。
计算最小执行时间：

根据最大频次和冷却时间计算最小时间：
任务调度中，最频繁的任务会限制整体的执行时间。我们需要给它们之间加上冷却时间。
如果最频繁任务的出现次数是 maxFreq，那么这些任务之间至少需要 (maxFreq - 1) * (coolDown + 1) 的时间。
由于可能有多个任务频率与 maxFreq 相同，我们需要考虑这些任务如何填充任务空隙。
最终结果是：max((maxFreq - 1) * (coolDown + 1) + countMaxFreq, tasks.length)。这样可以保证即使冷却时间调整后，至少能保证每个任务的执行

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象读取输入
        Scanner sc = new Scanner(System.in);

        // 读取任务列表并拆分成字符串数组
        String[] inputTasks = sc.next().split(",");
        int[] tasks = new int[inputTasks.length];
        
        // 将任务列表字符串数组转为整数数组
        for (int i = 0; i < inputTasks.length; i++) {
            tasks[i] = Integer.parseInt(inputTasks[i]);
        }
        
        // 读取冷却时间
        int coolDown = sc.nextInt();

        // 调用 minExecTime 函数计算最小执行时间并输出
        System.out.println(minExecTime(tasks, coolDown));
    }

    // 计算最小执行时间
    public static int minExecTime(int[] tasks, int coolDown) {
        // 创建一个 HashMap 用于统计每个任务的出现频次
        HashMap<Integer, Integer> freqMap = new HashMap<>();

        // 遍历任务数组并统计每个任务的频率
        for (int task : tasks) {
            freqMap.put(task, freqMap.getOrDefault(task, 0) + 1);
        }

        // 获取任务中出现次数最多的频率
        int maxFreq = freqMap.values().stream().max(Integer::compareTo).orElse(0);
        
        // 统计最大频率的任务个数
        int countMaxFreq = 0;
        for (int freq : freqMap.values()) {
            if (freq == maxFreq) countMaxFreq++;
        }

        // 计算最短执行时间：
        // (maxFreq - 1) * (coolDown + 1) 是最频繁任务的最短间隔时间
        // countMaxFreq 是填充这些间隔的额外任务数
        // 返回值是 (间隔时间 + 任务数量) 的最大值，确保任务数量足够
        return Math.max((maxFreq - 1) * (coolDown + 1) + countMaxFreq, tasks.length);
    }
}