LeetCode Task Scheduler

· 240 words · 2 minute read
2017年6月
LeetCode-贪心

621. Task Scheduler

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 1:

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

方法

贪心算法

  • 可以把一次调度看成为n+1的环，必须由不同的task来填，如果没有，则使用cpu idle状态来填
  • 尽量使用出现次数多的Task来填，尽量使用其他的task来隔开出现次数最多的Task.
  • 首先记录每个Task出现的次数，不需要知道Task的名称，放到递减的PriorityQueue。出现次数最多的Task会先出队列。根据环的长度进行遍历，每次遍历时，把PriorityQueue中的Task出队列，如果环被填满，则把出队列的Task全部减1，再添加到PriorityQueue中去。如果环没有被填满，则需要cpu的idle状态进行补充。

  • 注意两点。

    1. 把Task添加回PriorityQueue时候，如果Task剩余次数为0，则不能添加回去，说明调度完了。

    2. 如果一个环执行完了，发现没有Task没有添加到PriorityQueue中，即PriorityQueue为null,说明Task调度完了，这是最后一次调度，只需要添加实际的调度时间。

      public class Solution {

    public int leastInterval(char[] tasks, int n) {
        Map<Character,Integer> map = new HashMap<>();
        for(char c : tasks){
            if(map.containsKey(c)){
                int count = map.get(c);
                count++;
                map.put(c,count);
            }else{
                map.put(c,1);
            }
        }
        //使堆单调递减
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b-a);
        pq.addAll(map.values());

        int alltime = 0;
        int circle = n + 1;
        while(!pq.isEmpty()){
            List<Integer> list = new ArrayList<Integer>();
            int work = 0;
            for(int i = 0; i < circle; i++){
                if(!pq.isEmpty()){
                    list.add(pq.poll());
                    work++;
                }
            }
            for(Integer in : list){
                if(--in > 0){
                    pq.add(in);
                }
            }
            if(!pq.isEmpty()){
                alltime = alltime + circle;
            }else{
                alltime = alltime + work;
            }
        }
        return alltime;
    }
}
Share