621. Task Scheduler

/*
Time Complexity: O(M * logM)
Space Complexity: O(M)
M = length of the tasks array

When printing the Ordered string.. Time Complexity: O(M * logM + Idle Slots)
*/
class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (tasks == null || tasks.length == 0) {
            return 0;
        }
        if (n == 0 || tasks.length == 1) {
            return tasks.length;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<Map.Entry<Character, Integer>>(new Comparator<Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
                return b.getValue() - a.getValue();
            }
        });

        queue.addAll(map.entrySet());

        int currTime = 0;
        // StringBuilder sb = new StringBuilder();

        while (!queue.isEmpty()) {
            int k = n + 1;
            ArrayList<Map.Entry<Character, Integer>> tempList = new ArrayList<>();
            while (k > 0 && !queue.isEmpty()) {
                Map.Entry<Character, Integer> topEntry = queue.poll();
                topEntry.setValue(topEntry.getValue() - 1);
                // sb.append(topEntry.getKey());
                tempList.add(topEntry);
                k--;
                currTime++;
            }

            for (Map.Entry<Character, Integer> entry : tempList) {
                if(entry.getValue() > 0) {
                    queue.offer(entry);
                }
            }

            if (!queue.isEmpty()) {
                currTime += k;
                // for (int i = 0; i < k; i++) {
                //     sb.append(" ");
                // }
            }
        }
        // System.out.println(sb.toString());
        return currTime;
    }
}


/*
Refer: https://leetcode.com/problems/task-scheduler/discuss/104496/concise-Java-Solution-O(N)-time-O(26)-space

Time Complexity: O(n)
Space Complexity: O(1)
*/
class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (tasks == null || tasks.length == 0) {
            return 0;
        }
        if (n == 0 || tasks.length == 1) {
            return tasks.length;
        }

        int[] counts = new int[26];
        for (char task : tasks) {
            counts[task - 'A']++;
        }
        Arrays.sort(counts);
        int i = 25;

        while (i >= 0 && counts[i] == counts[25]) {
            i--;
        }

        /*
        (counts[25]-1) = Number of frames = Highest frequency - 1
        (n+1) = Frame Size
        (25-i) = Number of delimiters or Number of tasks with highest frequency.
        */
        return Math.max(tasks.length, (counts[25]-1) * (n+1) + (25-i));
    }
}


/*
If order has to be maintained, follow below soultion.

Time Complexity: O(M)
Space Complexity: O(M)
M = length of tasks array
*/
class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (tasks == null || tasks.length == 0) {
            return 0;
        }
        if (n == 0 || tasks.length == 1) {
            return tasks.length;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        int currTime = 0;

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

            if (!map.containsKey(tasks[i]) || currTime - map.get(tasks[i]) > n) {
                map.put(tasks[i], currTime);
                i++;
            }
        }

        return currTime;
    }
}