Task Scheduler

Description

https://leetcode.com/problems/task-scheduler/description/

Idea

The key of this problem is how to manipulate the order. First we should collect the count of each character.

Then we can image the box of n + 1 empty position which need to be filled by the given character. The solution chain should be contained of several box linked together(except for the last box).Each time when we are filling one box. We will fetch the character based on the count of the character in the priority queue.

In last iteration, there is no need to fill the n + 1 slots.

Solution

import java.util.PriorityQueue;
class Solution {
    
    public int leastInterval(char[] tasks, int n) {
        
        HashMap<Character, Integer> counter = new HashMap<>();
        for (char task : tasks) {
            Integer count = counter.get(task);
            if (count == null)
                counter.put(task, 1);
            else
                counter.put(task, count + 1);   
        }
        Queue<Integer> queue = new PriorityQueue<Integer>(
            new Comparator<Integer>() {
                public int compare(Integer a, Integer b) {
                    return b - a;
                }
            }
        );
        for ( Integer item : counter.values() ) {
            queue.add(item);
        }
        //Simulate the scenorio
        int length = 0;
        while( queue.isEmpty() == false) {
            int round = 0;
            LinkedList<Integer> remains = new LinkedList<>();
            for(int i = 0; !queue.isEmpty() && i < n + 1; i++){
                Integer remain = queue.remove();
                if(remain > 1) remains.add(remain-1);
                round += 1;
            }
            for (Integer remain : remains) {
                queue.add(remain);
            }
            length += queue.isEmpty() ? round : n + 1;
        }
        return length;
    }
    
}