621. Task Scheduler

Version #1 

好久没写java了，自己磕磕绊绊写了一版

用到了hashmap，没有利用tasks[i] is upper-case English letter这个条件

Time O(n)

Space O(1)

class Solution {

    public int leastInterval(char[] tasks, int n) {

        // A -> x -> x -> A -> x -> x -> A

        // (count(max chars) - 1) * (n + 1) + #chars that have max count

        if (n == 0) {

            return tasks.length;

        }

        int maxCount = 0;

        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < tasks.length; i++) {

            int cnt = map.getOrDefault(tasks[i], 0) + 1;

            maxCount = Math.max(maxCount, cnt);

            map.put(tasks[i], cnt);

        }

        int maxTasks = 0;

        for (Integer cnt : map.values()) {

            if (maxCount == cnt) {

                maxTasks++;

            }

        }

        return Math.max((maxCount - 1) * (n + 1) + maxTasks, tasks.length);

    }

}

Version #2 Optimized solution

Time O(n)

Space O(1)

这个testcase两次都错了

["A","A","A","B","B","B", "C","C","C", "D", "D", "E"]

2

class Solution {

    public int leastInterval(char[] tasks, int n) {

        // calculate the characters with max count

        int[] counts = new int[26];

        int maxCount = 0;

        int maxCountCharNum = 0;

        for (char task : tasks) {

            int i = task - 'A';

            counts[i]++;

            if (counts[i] > maxCount) {

                maxCountCharNum = 1;

                maxCount = counts[i];

            } else if (counts[i] == maxCount) {

                maxCountCharNum++;

            }

        }

        // n = 2

        // maxCountCharNum

        // (A B C) _divider_ (A B C) _ (A B C)

        // maxChars need (maxCount - 1) dividers to be seaparated

        // divider length = n - maxCountCharNum + 1

        // e.g. n = 2, maxCountCharNum = 1

        // A _ _ A _ _  divider = 2-1+1=2

        // if divider length <= 0 it means we don't need idle

        // e.g. n = 1, maxCountCharNum = 2

        // A B A B

        // so divider length = Math.max(0, n - maxCountCharNum + 1)

        // left chars = total chars - maxCountCharNum * maxCount

        // white spaces = divider length * (maxCount - 1) - left chars

        int idleCount = Math.max(0, n - maxCountCharNum + 1) * (maxCount - 1) - (tasks.length - maxCountCharNum * maxCount);

        return tasks.length + Math.max(0, idleCount);

    }

}