最佳CPU任务安排

最佳CPU任务安排

问题描述

有一条任务队列,其中每个任务用一个大写的字母表示,CPU在执行任务时,两个相同任务之间的最大间隔最少是一个给定的值n,不同任务之间可以没有空闲(间隔),求CPU执行的最小周期数(每一个空闲也算一个周期)。

image-20201123095843719

解决方法

  1. 贪心算法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
    22
    public 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;
    }
  2. 优先队列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
    30
    public 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任务安排/
作者
Chen Shuwen
发布于
2023年1月10日
许可协议