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

叁歲伎倆 2022-09-14 13:29 170阅读 0赞

## 题目 ##

[https://leetcode.com/problems/task-scheduler/][https_leetcode.com_problems_task-scheduler]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

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

后来又想了想，大概明白了，理解如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**解释**

因为最下面一层一定是出现次数最多的 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);
        }
    }

[https_leetcode.com_problems_task-scheduler]: https://leetcode.com/problems/task-scheduler/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e7528c6aa83744be9882da71edcbace4.png
[https_leetcode-cn.com_problems_task-scheduler_solution_tong-zi-by-popopop]: https://leetcode-cn.com/problems/task-scheduler/solution/tong-zi-by-popopop/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/72da44efef1a4a208dbe2a2e8af61f95.png