最佳CPU任务安排
最佳CPU任务安排
问题描述
有一条任务队列,其中每个任务用一个大写的字母表示,CPU在执行任务时,两个相同任务之间的最大间隔最少是一个给定的值n,不同任务之间可以没有空闲(间隔),求CPU执行的最小周期数(每一个空闲也算一个周期)。
解决方法
贪心算法O(tasks.length)
显然,要想让任务周期最短,数量最多的任务的处理方式是最重要的,当该任务处理完毕后,剩下的任务可以采取插空的方法。比如3A,2B,1C,n=2,此时先放A,得到A##A##A,那么实际空闲数等于(Count(A)-1)*n-(Count(tasks)-Count(A))和0中较大的那个。如果有多个最大值,则可以将他们捆绑起来看,比如3A,3B,1C,n=2, 则AB#AB#AB->X#X#X,此时空闲数=max(0,(Count(A)-1)*(n-maxCount+1)-(Count(tasks)-Count(A))),如果n-maxCount+1为负数,则说明空闲已经被挤占完 了,不会影响最终结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public int leastInterval(char[] tasks, int n) {
int[] counter = new int[26];
int max = 0;
int maxCount = 0;
for (char task : tasks) {
counter[task - 'A']++;
if (max == counter[task - 'A']) {
maxCount++;
} else if (max < counter[task - 'A']) {
max = counter[task - 'A'];
maxCount = 1;
}
}
int partCount = max - 1;
int partLength = n - (maxCount - 1);
int emptySlots = partCount * partLength;
int availableTasks = tasks.length - max * maxCount;
int idles = Math.max(0, emptySlots - availableTasks);
return tasks.length + idles;
}优先队列O(n*tasks.length)
先统计每个任务的数目,在安排任务时,依次安排任务数最多的任务,直到所有的任务被安排完。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> counts = new HashMap<Character, Integer>();
for (char t : tasks) {
counts.put(t, counts.getOrDefault(t, 0) + 1);
}
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
pq.addAll(counts.values());
int alltime = 0;
int cycle = n + 1;
while (!pq.isEmpty()) {
int worktime = 0;
List<Integer> tmp = new ArrayList<Integer>();
for (int i = 0; i < cycle; i++) {
if (!pq.isEmpty()) {
tmp.add(pq.poll());
worktime++;
}
}
for (int cnt : tmp) {
if (--cnt > 0) {
pq.offer(cnt);
}
}
alltime += !pq.isEmpty() ? cycle : worktime;
}
return alltime;
}
最佳CPU任务安排
http://example.com/2023/01/10/最佳CPU任务安排/