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);
}
}``````