Task Scheduler
Given a char array representing tasks CPU need to do. It contains capital letters A to Z. Each capital letter represents a different task. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could complete one task or be idle. However, there is a constraint that at any moment, two same tasks should have at least n intervals. You need to return the least number of intervals the CPU will take to finish all the tasks.
Constraints:
- 1 <= task.length <= 50000
- n is a non-negative integer
Examples:
Input: ["A","A","A","B","B","B"], 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B
Solutions
Greedy Algorithm
The idea is to use a map to store the frequency of each task. Then we find the maximum frequency and the number of tasks with this frequency. The answer is the maximum of the total number of tasks and (maxCount - 1) * (n + 1) + maxCountTask.
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> map = new HashMap<>();
for (char task : tasks) {
map.put(task, map.getOrDefault(task, 0) + 1);
}
int maxCount = 0, maxCountTask = 0;
for (int count : map.values()) {
if (count > maxCount) {
maxCount = count;
maxCountTask = 1;
}
else if (count == maxCount) {
maxCountTask++;
}
}
return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxCountTask);
}Follow-up:
What if we have multiple CPUs and we want to find the least number of intervals to finish all the tasks?
