[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)：

	class Solution {
	public:
	int leastInterval(vector<char>& tasks, int n) {
	if(n <= 0)return tasks.size();
	vector<int> count(26);
	for(char c : tasks)
	++count[c - 'A'];
	priority_queue<int> pq;
	for(auto& i : count)
	if(i)
	pq.push(i);
	//cooling time
	queue<int> freeze;
	int len = 0, group = n + 1;
	while(pq.size() || freeze.size())
	{
	if(pq.size())
	{
	if(pq.top() > 1)
	freeze.push(pq.top() - 1);
	pq.pop();
	}
	if(--group == 0)//safe to release freezed tasks
	{
	while(freeze.size())
	{
	pq.push(freeze.front());
	freeze.pop();
	}
	group = n + 1;
	}
	++len;
	}
	return len;
	}
	};

view raw Task Scheduler.cpp hosted with ❤ by GitHub