621. 任务调度器

这题最重要的是首先找到出现次数最多的任务,然后根据n把最多次数的先排序,然后在之间的空位可以考虑是放别的任务还是空位我们想想看,如果我们直接找任务次数小的任务,那么多的任务不知道改怎么放所以这题最重要的就是1.把每个任务的出现次数统计保存2.找到出现次数最多的任务3.使用公式得到答案先学会“摆格子”因为代码其实就是公式。第一步统计每个任务出现次数比如[A,A,A,B,B,B]统计A - 3 B - 3Javaint[] count new int[26]; for (char c : tasks) { count[c - A]; }这里A - A 0 B - A 1所以count[0] A 的数量 count[1] B 的数量第二步找到最大频率比如A - 3 B - 3 C - 1最大频率maxFreq 3代码int maxFreq 0; for (int c : count) { maxFreq Math.max(maxFreq, c); }第三步有几个任务并列第一这里A - 3 B - 3所以maxCount 2代码int maxCount 0; for (int c : count) { if (c maxFreq) { maxCount; } }第四步套公式核心公式(maxFreq - 1) * (n 1) maxCount为什么是这个公式举例A A A n 2先把 A 固定A _ _ A _ _ A你会发现有maxFreq - 1个“空档”这里3 - 1 2每个空档长度n 1因为A _ _长度是 3。所以(3 - 1) * (2 1) 6最后再加最后一个 A1得到7为什么最后不是 1 而是 maxCount因为可能A A A B B B最后一排A B所以2最后为什么还要 max因为有时候任务很多。可以把空位填满。比如A A A B B B C D E F根本不需要 idle。所以答案不能小于tasks.length因此Math.max(tasks.length, 公式值)完整代码class Solution { public int leastInterval(char[] tasks, int n) { // 统计每个任务出现次数 int[] count new int[26]; for (char c : tasks) { count[c - A]; } // 找最大频率 int maxFreq 0; for (int c : count) { maxFreq Math.max(maxFreq, c); } // 找有几个并列最大频率 int maxCount 0; for (int c : count) { if (c maxFreq) { maxCount; } } // 套公式 return Math.max( tasks.length, (maxFreq - 1) * (n 1) maxCount ); } }面试时怎么解释你可以这样说出现次数最多的任务决定整体框架。先按冷却时间把最高频任务排开再用其他任务填空。如果填不满就需要 idle。