#P3222. 任务最优调度(200分)
-
1000ms
Tried: 70
Accepted: 25
Difficulty: 5
所属公司 :
华为od
任务最优调度(200分)
题面描述
给定一个正整数数组表示待系统执行的任务列表,数组的每一个元素代表一个任务,元素的值表示该任务的类型。
请计算执行完所有任务所需的最短时间。
任务执行规则如下:
- 任务可以按任意顺序执行,且每个任务执行耗时间均为 1 个时间单位。
- 两个同类型的任务之间必须有长度为 N 个单位的冷却时间,比如 N 为 2 时,在时间 K 执行了类型 3 的任务,那么 K+1 和 K+2 两个时间不能执行类型 3 的任务。
- 系统在任何一个单位时间内都可以执行一个任务,或者等待状态。
思路
此问题类似于经典的任务调度问题(如LeetCode上的"Task Scheduler")。核心思想是:
-
统计每种任务的频率:首先统计每种任务出现的次数,找出出现次数最多的任务类型及其数量。
-
计算最小时间:
- 假设出现次数最多的任务有
max_freq次,且有max_count种任务拥有这个频率。 - 任务的最小执行时间可以通过公式计算: 时间=(max_freq=-1)*(N+1)+max_count
- 这个公式的含义是:将
max_freq - 1个任务块(每个块的长度为N + 1),最后加上max_count个任务。
- 假设出现次数最多的任务有
-
取最大值:最终的最小时间是上述计算结果和任务总数中的较大者,因为有时候任务总数已经足够多,不需要等待。
具体步骤
-
统计任务频率:使用一个大小为1001的数组
freq来统计每种任务的出现次数,同时记录出现次数最多的任务频率max_freq。 -
确定最大频率任务的数量:遍历
freq数组,统计有多少种任务的频率等于max_freq,记为max_count。 -
计算最小时间:
- 计算需要的块数
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 个时间单位
- 两个同类型的任务之间必须有长度为 N 个单位的冷却时间,比如 N 为 2 时,在时间 K 执行了类型 3 的任务,那么 K+1 和 K+2 两个时间不能执行类型 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 。