//leetcode submit region begin(Prohibit modification and deletion)

class Solution {

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

PriorityQueue<Pair<Character, Integer>> pq = new PriorityQueue<>(new Comparator<Pair<Character, Integer>>() {

@Override

public int compare(Pair<Character, Integer> o1, Pair<Character, Integer> o2) {

if(o1.getValue() < o2.getValue())

return 1;

else if(o1.getValue() > o2.getValue())

return -1;

else

return 0;

}

});

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

for(char c : tasks)

map.put(c, map.getOrDefault(c, 0) + 1);

for(Map.Entry<Character, Integer> entry : map.entrySet())

pq.add(new Pair<>(entry.getKey(), entry.getValue()));

int time = 0;

while(!pq.isEmpty()) {

List<Pair<Character, Integer>> temp = new ArrayList<>();

int i = 0;

while(i <= n) {

if(pq.peek() != null) {

Pair<Character, Integer> pair = pq.poll();

if(pair.getValue() > 1) {

temp.add(new Pair<>(pair.getKey(), pair.getValue() - 1));

}

}

time++;

if(pq.isEmpty() && temp.isEmpty())

break;

i++;

}

pq.addAll(temp);

}

return time;

}

}

//leetcode submit region end(Prohibit modification and deletion)

public static void main(String[] args) {

Solution solution = new TaskScheduler().new Solution();

}

}