题面描述

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

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

任务执行规则如下:

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

思路

此问题类似于经典的任务调度问题（如LeetCode上的"Task Scheduler"）。核心思想是：

1. 统计每种任务的频率：首先统计每种任务出现的次数，找出出现次数最多的任务类型及其数量。

2. 计算最小时间：

   • 假设出现次数最多的任务有 max_freq 次，且有 max_count 种任务拥有这个频率。
   • 任务的最小执行时间可以通过公式计算： 时间=(max_freq=-1)*(N+1)+max_count
   • 这个公式的含义是：将 max_freq - 1 个任务块（每个块的长度为 N + 1），最后加上 max_count 个任务。

3. 取最大值：最终的最小时间是上述计算结果和任务总数中的较大者，因为有时候任务总数已经足够多，不需要等待。

具体步骤

1. 统计任务频率：使用一个大小为1001的数组freq来统计每种任务的出现次数，同时记录出现次数最多的任务频率max_freq。

2. 确定最大频率任务的数量：遍历freq数组，统计有多少种任务的频率等于max_freq，记为max_count。

3. 计算最小时间：

   • 计算需要的块数part_count = max_freq - 1。
   • 每个块的长度为N + 1，即执行一个任务后需要等待N个时间单位。
   • 总的空槽时间为part_count * part_length，再加上max_count个任务。
   • 最终的最小时间是上述计算结果与任务总数的最大值。

cpp

#include <bits/stdc++.h>
using namespace std;

int leastInterval(vector<int>& tasks, int N) {
    // 统计每种任务的频率
    vector<int> freq(1001, 0);
    int max_freq = 0;
    for(auto task: tasks){
        freq[task]++;
        max_freq = max(max_freq, freq[task]);
    }
    
    // 计算拥有最大频率的任务数量
    int max_count = 0;
    for(auto f: freq){
        if(f == max_freq) max_count++;
    }
    
    // 计算最小时间
    int part_count = max_freq - 1;
    int part_length = N + 1;
    int empty_slots = part_count * part_length + max_count;
    
    // 返回最大值
    return max((int)tasks.size(), empty_slots);
}

int main(){
    string s;
    getline(cin, s);
    // 分割输入字符串
    vector<int> tasks;
    string num = "";
    for(char c: s){
        if(c == ','){
            if(!num.empty()){
                tasks.push_back(stoi(num));
                num = "";
            }
        }
        else{
            num += c;
        }
    }
    if(!num.empty()) tasks.push_back(stoi(num));
    
    int N;
    cin >> N;
    
    cout << leastInterval(tasks, N);
}

python

# Python 解法

def leastInterval(tasks, N):
    # 统计每种任务的频率
    freq = {}
    max_freq = 0
    for task in tasks:
        freq[task] = freq.get(task, 0) + 1
        if freq[task] > max_freq:
            max_freq = freq[task]
    
    # 计算拥有最大频率的任务数量
    max_count = 0
    for f in freq.values():
        if f == max_freq:
            max_count += 1
    
    # 计算最小时间
    part_count = max_freq - 1
    part_length = N + 1
    empty_slots = part_count * part_length + max_count
    
    # 返回最大值
    return max(len(tasks), empty_slots)

if __name__ == "__main__":
    import sys
    # 读取任务列表
    s = sys.stdin.readline().strip()
    tasks = list(map(int, s.split(',')))
    # 读取冷却时间
    N = int(sys.stdin.readline())
    # 输出结果
    print(leastInterval(tasks, N))

java

import java.util.*;

public class Main {
    public static int leastInterval(int[] tasks, int N) {
        // 统计每种任务的频率
        int[] freq = new int[1001];
        int max_freq = 0;
        for(int task: tasks){
            freq[task]++;
            if(freq[task] > max_freq){
                max_freq = freq[task];
            }
        }
        
        // 计算拥有最大频率的任务数量
        int max_count = 0;
        for(int f: freq){
            if(f == max_freq){
                max_count++;
            }
        }
        
        // 计算最小时间
        int part_count = max_freq - 1;
        int part_length = N + 1;
        int empty_slots = part_count * part_length + max_count;
        
        // 返回最大值
        return Math.max(tasks.length, empty_slots);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取任务列表
        String s = sc.nextLine();
        String[] parts = s.split(",");
        int[] tasks = new int[parts.length];
        for(int i=0;i<parts.length;i++) {
            tasks[i] = Integer.parseInt(parts[i]);
        }
        // 读取冷却时间
        int N = sc.nextInt();
        // 输出结果
        System.out.println(leastInterval(tasks, N));
    }
}

题目内容

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

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

任务执行规则如下:

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

输出

7

说明

时间$1$：执行类型 $2$ 任务。

时间$2$：执行类型 $3$ 的任务（因为冷却时间为 $2$ ，所以时间 $2$ 不能执行类型 $2$ 的任务）。

时间$3$：系统等待（仍然在类型 $2$ 的冷却时间）。

时间$4$：执行类型 $2$ 任务。

时间$5$：系统等待。

时间$6$：系统等待。

时间$7$：执行类型 $2$ 任务。

因此总共耗时 $7$ 。