package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * https://leetcode.com/problems/task-scheduler/
 */
public class Problem621 {
    public int leastInterval(char[] tasks, int n) {
        int result = 0;
        Map<Character, Integer> charCountMap = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            if (!charCountMap.containsKey(tasks[i])) {
                charCountMap.put(tasks[i], 1);
            } else {
                charCountMap.put(tasks[i], charCountMap.get(tasks[i]) + 1);
            }
        }
        PriorityQueue<CharCount> queue = new PriorityQueue<>((a, b) -> {
            int cmp = Integer.compare(b.count, a.count);
            if (cmp == 0) {
                return Integer.compare(a.ch, b.ch);
            }
            return cmp;
        });
        charCountMap.forEach((ch, count) -> queue.add(new CharCount(ch, count)));
        Set<Character> processed = new HashSet<>();
        List<CharCount> tmp = new ArrayList<>();
        while (!queue.isEmpty()) {
            boolean found = false;
            CharCount charCount = null;
            while (!queue.isEmpty()) {
                charCount = queue.poll();
                if (processed.contains(charCount.ch)) {
                    tmp.add(charCount);
                    continue;
                }
                found = true;
                break;
            }
            if (!found) {
                result += n - processed.size() + 1;
                processed.clear();
            } else {
                charCount.count--;
                if (charCount.count > 0) {
                    queue.add(charCount);
                }
                processed.add(charCount.ch);
                if (processed.size() == n + 1) {
                    processed.clear();
                }
                result++;
            }
            for (CharCount cc : tmp) {
                queue.add(cc);
            }
            tmp.clear();
        }
        return result;
    }

    private static class CharCount {
        private final char ch;
        private int count;

        public CharCount(char ch, int count) {
            this.ch = ch;
            this.count = count;
        }

        @Override
        public String toString() {
            return ch + " -> " + count;
        }
    }

    public static void main(String[] args) {
        Problem621 prob = new Problem621();
        System.out.println(prob.leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
        System.out.println(prob.leastInterval(new char[]{'A','A','A','B','B','B'}, 1)); // 6
        System.out.println(prob.leastInterval(new char[]{'A','A','A','B','B','B'}, 3)); // 10
        System.out.println(prob.leastInterval(new char[]{'A','B','B','B'}, 2)); // 7
        System.out.println(prob.leastInterval(new char[]{'A','B','B','B'}, 1)); // 5
        System.out.println(prob.leastInterval(new char[]{'A','B','C'}, 1)); // 3
        System.out.println(prob.leastInterval(new char[]{'A','B','C'}, 2)); // 3
        System.out.println(prob.leastInterval(new char[]{'A','B','C'}, 3)); // 3
        System.out.println(prob.leastInterval(new char[]{'A','B','C','A'}, 3)); // 5
        System.out.println(prob.leastInterval(new char[]{'A','B','C','A','C'}, 3)); // 6
        System.out.println(prob.leastInterval(new char[]{'A','B','C','D','C'}, 3)); // 5
        System.out.println(prob.leastInterval(new char[]{'A','B','B','C','C','D','D','D','E'}, 3)); // 9
        System.out.println(prob.leastInterval(new char[]{'A','B','B','C','C','D','D','D','E'}, 4)); // 11
    }
}

@@ -70,34 +70,8 @@
 ap;%0A
-import java.util.HashSet;%0A
 impo
@@ -85,24 +85,24 @@
 .util.List;%0A
+
 import java.
@@ -146,30 +146,8 @@
 eue;
-%0Aimport java.util.Set;
 %0A%0A/*
@@ -993,22 +993,17 @@
     
-Set%3CCharacter%3E
+boolean%5B%5D
  pro
@@ -1019,19 +1019,51 @@
 new 
-HashSet%3C%3E()
+boolean%5B26%5D;%0A        int processedCount = 0
 ;%0A  
@@ -1333,18 +1333,9 @@
 ssed
-.contains(
+%5B
 char
@@ -1342,17 +1342,23 @@
 Count.ch
-)
+ - 'A'%5D
 ) %7B%0A    
@@ -1573,23 +1573,21 @@
 rocessed
-.size()
+Count
  + 1;%0A  
@@ -1605,32 +1605,78 @@
    processed
-.clear()
+ = new boolean%5B26%5D;%0A                processedCount = 0
 ;%0A          
@@ -1849,21 +1849,17 @@
 rocessed
-.add(
+%5B
 charCoun
@@ -1862,17 +1862,64 @@
 Count.ch
-)
+ - 'A'%5D = true;%0A                processedCount++
 ;%0A      
@@ -1945,15 +1945,13 @@
 ssed
-.size()
+Count
  == 
@@ -1988,24 +1988,74 @@
 rocessed
-.clear()
+ = new boolean%5B26%5D;%0A                    processedCount = 0
 ;%0A      
@@ -2448,32 +2448,32 @@
 .count = count;%0A
+
         %7D%0A%0A     
@@ -2469,1375 +2469,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return ch + %22 -%3E %22 + count;%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem621 prob = new Problem621();%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','A','A','B','B','B'%7D, 2)); // 8%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','A','A','B','B','B'%7D, 1)); // 6%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','A','A','B','B','B'%7D, 3)); // 10%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','B','B'%7D, 2)); // 7%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','B','B'%7D, 1)); // 5%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','C'%7D, 1)); // 3%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','C'%7D, 2)); // 3%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','C'%7D, 3)); // 3%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','C','A'%7D, 3)); // 5%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','C','A','C'%7D, 3)); // 6%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','C','D','C'%7D, 3)); // 5%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','B','C','C','D','D','D','E'%7D, 3)); // 9%0A        System.out.println(prob.leastInterval(new char%5B%5D%7B'A','B','B','C','C','D','D','D','E'%7D, 4)); // 11
 %0A   

Solve problem 621