BiruLyu
7/3/2017 - 3:50 AM

621. Task Scheduler(1st).java

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (tasks == null) return 0;
        int len = tasks.length;
        Map<Character, Integer> map = new HashMap<>();
        int maxFrequency = 0;
        for (char c : tasks) {
            map.put(c, map.getOrDefault(c, 0) + 1);
            maxFrequency = Math.max(maxFrequency, map.get(c));
        }
        int count = 0;
        for (int frequency : map.values()) {
            if (frequency == maxFrequency) {
                count++;
            }
        }
        return Math.max(len, (maxFrequency - 1) * (n + 1)  + count);
    }
}
public class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : tasks) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> e2 - e1);
        queue.addAll(map.values());
        int count = 0;
        while (!queue.isEmpty()) {
            int k = n + 1;
            List<Integer> next = new ArrayList<>();
            while (!queue.isEmpty() && k > 0) {
                int target = queue.poll();
                if (target - 1 > 0) {
                    next.add(target - 1);
                }
                count++;
                k--;
            }
            if (!next.isEmpty()) {
                count += k;
            }
            queue.addAll(next);
        }
        return count;
    }
}
public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] val = new int[26];
        for(int i = 0; i < tasks.length; i ++){
            val[tasks[i]-'A']++;
        }
        Arrays.sort(val);
        int i = 25;
        while(i>=0 && val[i]==val[25])i--;
        return Math.max(tasks.length, (val[25]-1)*(n+1)+25-i);
    }
}