leetcode 621. Task Scheduler | 621. 任务调度器（Java）

https://leetcode.com/problems/task-scheduler/

似懂非懂的答案，https://leetcode-cn.com/problems/task-scheduler/solution/tong-zi-by-popopop/，没有直观理解，又找不到反例。

后来又想了想，大概明白了，理解如下：

解释

因为最下面一层一定是出现次数最多的 task，所以其余的所有 task 都可以平铺在它的上面。把所有 task 想象成光滑的小方块，它们可以在不上下重叠的情况下，左右滑动，找到适合自己的位置，而且在找位置的时候，就像水往低处流那样，优先往高度较小的位置塞。这样一来，如果能塞满 n+1 的高度，说明可以不等待地紧密调度。如果不能塞满，就用空值把它统一塞回到 n+1 的高度。

（之前纠结的地方在于，会不会有些位置的高度已经溢出了，而另一些位置还没满？看起来是不存在这种情况的，因为水往低处流，先塞高度小的位置，始终保持不让高度差大于1。）

另外，关于如何理解返回时的 Math.max，我的解释是，要么能塞满，此时取 tasks.length，要么不能塞满，此时取 (maxTask - 1) * (n + 1) + countMaxTask。

class Solution {
    // https://leetcode-cn.com/problems/task-scheduler/solution/tong-zi-by-popopop/
    public int leastInterval(char[] tasks, int n) {
        int[] arr = new int[26];
        int countMaxTask = 0;
        int maxTask = 0;
        for (char c : tasks) {
            arr[c - 'A']++;
            maxTask = Math.max(arr[c - 'A'], maxTask);
        }

        for (int i = 0; i < 26; i++) {
            if (arr[i] == maxTask) {
                countMaxTask++;
            }
        }
        return Math.max(tasks.length, (maxTask - 1) * (n + 1) + countMaxTask);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.leastInterval(new char[]{'A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'E', 'E', 'E', 'E', 'F', 'G', 'H', 'H', 'H'}, 2);
    }
}