[LeetCode]Task Scheduler

因为有cooling time n的存在，当我们某个task t的数目越多，我们越需要找到更多的其他task去填补中间的idle time，让idle time最小，总的时间才可能最小。那么当我们每次schedule task的时候，我们应该从还不在冷却的task中找到数目最多的那一个，然后schedule它，否则的话，我们只能插入idle time。我们仍然需要证明这个算法能给我们最少的idle time。如果我们把这个过程用2D array表示（参考这篇文章底部的图），我们将最长的那条column不放在最左侧，那么为了满足冷却的条件，最底下一层最长column的左侧就必然会多出需要填补的slot，而集合总的task数量是一样的，那么相较于原算法必然会有可能产生更多的idle time。所以我们要优先schedule不在冷却中的数量最多的task。代码如下，虽然我们用了priority queue，但task种类最多只有26种没所以时间复杂度是O(n)：