题目描述

题解

排序

因为有n个间隔, 所以假设每轮执行n+1个任务, 按照当前各个任务的频次高低来执行. 也就是说频次高的任务优先执行. 如果把频次高的任务放在最后的话, 那么会有很多空闲时间.

每执行完一个任务就把该任务的频次降1, 每轮任务结束后都把数组重新排序, 更新优先级.

public int leastInterval(char[] tasks, int n) {
    int[] map = new int[26];

    for (char task : tasks) {
        map[task - 'A']++;
    }

    Arrays.sort(map);

    int time = 0;

    while (map[25] > 0) {
        int i = 0;
        while (i <= n) {
            if (map[25] == 0) {
                break;
            }
            if (i < 26 && map[25 - i] > 0) {
                map[25 - i]--;
            }
            time++;
            i++;
        }
        Arrays.sort(map);
    }
    return time;

}

桶思想

将每轮要执行的任务当成一个桶, 桶的大小为n+1. 桶的个数为频次最高的任务的频次.

假设有 5 个 A，5 个 B， 2 个 C

注意：桶并不是完整的矩形，最后一行由 max count 决定

摆列顺序：先放任务个数大的，再放小的；从上到下，从左到右放，如图（ - 代表待命）。

执行顺序：左到右，上到下

由图可知, 需要的总时间为(max-1)*(n+1)+maxCount, 其中maxCount就是频次最高且相同的任务的个数.

如果桶没有被填满, 那么空闲的格子代表的就是间隔时间.

但是如果这样设计的桶空间不够呢?

假设有 5 个 A，5 个 B， 3 个 C，2 个 D，2 个 E，2 个 F，1 个 G

摆放顺序：在前面的基础上，桶不够时往桶右边补，顺序仍然是从上到下，从左到右放，如图（浅色部分是桶外）

执行顺序：左到右，上到下

将超出的任务放在各个桶后面, 任务的执行顺序不变, 也就是说实际执行时一轮已经不是严格的n+1个任务了, 这样就不会有空闲时间, 锁花费的时间就是任务的数量.

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char task : tasks) {
        freq[task - 'A']++;
    }

    int max = 0;
    for (int i : freq) {
        max = Math.max(max, i);
    }

    int maxCount = 0;
    for (int i : freq) {
        if (i == max) {
            maxCount++;
        }
    }

    return Math.max((max - 1) * (n + 1) + maxCount, tasks.length);

}