621. Task Scheduler

Medium
我觉得,一个解法最要紧是能convince yourself. 很多lc高票答案看上去过于华丽,根本不好理解,无法使自己信服说ok I got it. 这样的解法还是不要了吧,宁愿去掌握那些看起来笨一点,但是Hell yeah I got it的那种解法,因为考到了你才真的能写出来,说出来思路,而不是抄了答案背了答案,让你说一下思路你根本是乱的。

讲解:https://www.youtube.com/watch?v=YCD_iYxyXoo

image.png

例如相同task之间至少要间隔n个interval,我们先计算出每个task出现的频率,找到出现频率最高的tasks. 比如这里我们知道task A出现的频率最高,频率为maxFreq = k. 我们就分k - 1个group,每个group里面有n + 1个slots. 为什么要分k - 1个不是k个呢,因为这k - 1个groups如果n + 1个slots不能用task填满的话需要用idle去填满,但最后一组我们可以不在尾部放idle. 所以最后一组比较特殊,所以我们才分成k - 1 groups + 1 last group.

image.png

这个题有一种特殊情况,会导致算出来的number of intervals < task.length. 这种情况为什么会发生呢,是因为我们按照 n + 1 slots计算的时候,可能并没把那些低频的task放进去,slots就不够了. 比如说上图中,我们前面3个group, 每个group有n + 1 = 3个slots. 我们按照高频到低频放,发现D, F, G这些低频的根本还没放完。 然而我们最后加the last group的时候只会加the highest frequency task, 这里就是A, 却不会特意去加上F,D,G这些低频任务,所以会导致我们算出来的number of intervals比任务总数还小,这个答案明显是invalid. 这时候比较容易看出来,我们不需要加任何idle interval就可以排tasks保证达到要求的cooling periods, 所以这种情况下答案就是task.length

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freqs = new int[26];
        for (char c : tasks){
            freqs[c - 'A']++;
        }
        Arrays.sort(freqs);
        int maxFreq = freqs[25];
        int maxCount = 0;
        for (int freq : freqs){
            if (freq == maxFreq){
                maxCount++;
            }
        }
        int ans = (maxFreq - 1) * ( n + 1) + count;
        return Math.max(ans, tasks.length);
    }
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 13,163评论 0赞 33
  • 贝贝, 妈妈已经两天没有和你说话了,不知道你今天在上海还好吗? 这两天妈妈爬山走了将近30公里山路,看到了许多美丽...
    lesley_75a6阅读 152评论 0赞 0
  • 我其实特别懒,就是那种明明有伞却不愿打开的懒。很奇怪吧,我想你可能看见了一个傻逼,因为她总是宁愿被太阳晒和被雨淋,...
    海上舟啊阅读 1,024评论 0赞 2
  • 今礼拜天,我在家大扫除。宝贝从他奶奶家回来 ,看见我在洗衣服。 马艺洳说:“妈妈洗衣服累不累呀”, 我就把问...
    马艺洳妈妈阅读 371评论 0赞 3
  • 最近总是想起你 以前觉得自己理解不了你 现在却不断的想去了解你 你最近在听什么歌 最近多久打一次球 还是不是和以前...
    zita_阅读 209评论 0赞 0

友情链接更多精彩内容