Formatted question description: https://leetcode.ca/all/621.html

Medium

## Description

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

## Solution

Use priority queue. Each element in the priority queue is an object that contains a task and the count of the task, where the task with the maximum count is polled fist.

Loop over tasks and count the number of each task, and for each task, create an object of the task and its count and offer the object into the priority queue.

Since the cooling interval n is given, doing n + 1 different tasks each round won’t have idle time. Therefore, each round select at most n + 1 objects of different tasks from the priority queue, update their counts and add the number of intervals to the total number of intervals. If there are remaining tasks, then add idle intervals if necessary. Then offer the updated objects to the priority queue.

Finally, return the total number of intervals.

• public class Task_Scheduler {

public class Solution_heap {
public int leastInterval(char[] tasks, int n) {
int[] map = new int[26];
map[c - 'A']++;
PriorityQueue<Integer> queue = new PriorityQueue<>(26, Collections.reverseOrder());
for (int f : map) {
if (f > 0)
}

// picking up the largest task from the queuequeue for current execution
int time = 0;
while (!queue.isEmpty()) {
int i = 0;
List<Integer> temp = new ArrayList<>();
while (i <= n) {
if (!queue.isEmpty()) {
if (queue.peek() > 1)
else
queue.poll();
}
time++;
if (queue.isEmpty() && temp.size() == 0)
break;
i++;
}
for (int l : temp)
}
return time;
}
}

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

int[] map = new int[26];

map[c - 'A']++;
}

Arrays.sort(map);

int time = 0;
while (map[25] > 0) {
int i = 0;
while (i <= n) {
if (map[25] == 0)
break;
if (i < 26 && map[25 - i] > 0)
map[25 - i]--;
time++;
i++;
}
Arrays.sort(map);
}

return time;
}
}

}

• Todo

• class Solution(object):
# O(nlogn) greedy to place most popular and distinct tasks first
# Actually, I don't think this is greedy
# We always place different tasks in a cycle which will minimize steps
# If not different tasks can be placed in a cycle, place an idle.
"""
:type n: int
:rtype: int
"""
n += 1
ans = 0
heap = [-c for c in d.values()]
heapq.heapify(heap)
while heap:
stack = []
cnt = 0
for _ in range(n):
if heap:
c = heapq.heappop(heap)
cnt += 1
if c < -1:
stack.append(c + 1)
for item in stack:
heapq.heappush(heap, item)
ans += heap and n or cnt  # == if heap then n else cnt
return ans

# O(n) # of the most frequent tasks, say longest, will determine the legnth
# to void counting idle intervals, we count (longest - 1) * (n + 1)
# then count how many will in the last cycle which means finding ties
# if counted number is less than # of tasks which means
# less frequent tasks can be always placed in such cycle
# and it won't cause any conflicts with requirement since even most frequent can be settle
# finally, return max(# of task, total counted number)
counts = d.values()
longest = max(counts)
ans = (longest - 1) * (n + 1)
for count in counts:
ans += count == longest and 1 or 0



Java

• class Solution {
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
count++;
}
Set<Character> set = map.keySet();
for (char task : set) {
}
int intervals = 0;
while (!priorityQueue.isEmpty()) {
int size = priorityQueue.size();
int curTasks = Math.min(size, n + 1);
for (int i = 0; i < curTasks; i++) {
}
intervals += curList.isEmpty() ? curTasks : n + 1;
}
return intervals;
}
}

public int count;

}

this.count = count;
}

else
}
}

• Todo

• class Solution(object):
# O(nlogn) greedy to place most popular and distinct tasks first
# Actually, I don't think this is greedy
# We always place different tasks in a cycle which will minimize steps
# If not different tasks can be placed in a cycle, place an idle.
"""
:type n: int
:rtype: int
"""
n += 1
ans = 0
heap = [-c for c in d.values()]
heapq.heapify(heap)
while heap:
stack = []
cnt = 0
for _ in range(n):
if heap:
c = heapq.heappop(heap)
cnt += 1
if c < -1:
stack.append(c + 1)
for item in stack:
heapq.heappush(heap, item)
ans += heap and n or cnt  # == if heap then n else cnt
return ans

# O(n) # of the most frequent tasks, say longest, will determine the legnth
# to void counting idle intervals, we count (longest - 1) * (n + 1)
# then count how many will in the last cycle which means finding ties
# if counted number is less than # of tasks which means
# less frequent tasks can be always placed in such cycle
# and it won't cause any conflicts with requirement since even most frequent can be settle
# finally, return max(# of task, total counted number)