LeetCode ： 621. Task Scheduler 任务规划

怼烎@ 2021-06-24 16:11 373阅读 0赞

**试题**  
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

Input: tasks = \[“A”,“A”,“A”,“B”,“B”,“B”\], n = 2  
Output: 8  
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

**代码**  
很显然我们这里要使用贪心算法。因为对于数量多的任务越早的执行就越能让它在后面获得一个更早执行的机会。一开始打算使用数量降序，前一个位置升序的优先队列。但存在一个问题就是如果数量多的话会一直占用次多的执行机会，所以位置升序没有用。转而使用一个把n+1个程序都挑选完。另外注意终止条件。

class Solution {
        public int leastInterval(char[] tasks, int n) {
            int[] AB = new int[26];
            for(char c : tasks){
                AB[c-'A'] += 1;
            }
            PriorityQueue<Integer> que = new PriorityQueue<Integer>(26, (a,b)->b-a);
            for(int cnt : AB){
                if(cnt!=0)
                    que.offer(cnt);
            }
            int res = 0;
            while(!que.isEmpty()){
                int n_cnt=0;
                ArrayList<Integer> temp = new ArrayList<Integer>();
    //             注意等于，因为间距n个，加上重复字母，也就是n+1个
                while(n_cnt<=n){
                    if(!que.isEmpty()){
                        if(que.peek()>1){
                            temp.add(que.poll()-1);
                        }else{
                            que.poll();
                        }
                    }
                    res += 1;
                    n_cnt += 1;
    //                 当最后的数量不足n+1个时，应该提前退出。
                    if(que.isEmpty() && temp.size()==0)
                        break;
                }
                for(int i : temp){
                    que.offer(i);
                }
            }
            return res;
        }
    }