621. Task Scheduler (Medium)
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 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
- The number of tasks is in the range [1, 10000].
- The integer n is in the range [0, 100].
这题是这个系列的第三个：不保持顺序输出时间。此题有五个变种。保持顺序输出时间，保持顺序输出顺序，不保持顺序输出时间，不保持顺序输出顺序，如果tasks很多 但是cooldown time很小 如何优化空间复杂度到 O(cooldown time)注意这里顺序是不能变的。
Special case: ["A","A","A","B","B","B"] 0，按公式算出是4，实际结果是6
["A","A","A","B","B","B","C"] n = 2, the size of frame is 2 + 1 =3, the number of frame is 3 - 1 =2, the size of extra frame（AB） is 2. So the result is 2 * 3 + 2 = 8.
First consider the most frequent characters, we can determine their relative positions first and use them as a frame to insert the remaining less frequent characters. Here is a proof by construction:
Let F be the set of most frequent chars with frequency k.
We can create k chunks, each chunk is identical and is a string consists of chars in F in a specific fixed order.
Let the heads of these chunks to be H_i; then H_2 should be at least n chars away from H_1, and so on so forth; then we insert the less frequent chars into the gaps between these chunks sequentially one by one ordered by frequency in a decreasing order and try to fill the k-1 gaps as full or evenly as possible each time you insert a character.In summary, append the less frequent characters to the end of each chunk of the first k-1 chunks sequentially and round and round, then join the chunks and keep their heads’ relative distance from each other to be at least n.
Solution 1: HashMap + Greedy O(n); O(1)
因为只有26个task，O(1) space，但是如果范围是int，那空间复杂度就是O(n)了，follow up会让优化这个。
public int leastInterval(char[] tasks, int cooldown) { //面试中一般会给一个int数组。
// map: task -> frequency of occurrences
Map<Integer, Integer> map = new HashMap<>(); //如果范围只有26个字符，可以用int数组模拟hashmap，代码就不写了
for (int task : tasks) {
map.put(task, map.getOrDefault(task, 0) + 1);
}
int maxFrequency = 0, maxCount = 0;
for (int frequency : map.values()) { //在一组数据中找最大值和最大值出现次数，不需要排序
if (frequency > maxFrequency) {
maxFrequency = frequency;
maxCount = 1;
} else if (frequency == maxFrequency) {
maxCount++;
}
}
// 这个计算公式需要具体分析
int minTime = (maxFrequency - 1) * (cooldown + 1) + maxCount;
// 填坑的时候，有可能坑填满了，但是还有task没被放进去，这时候输出input.length即可
return Math.max(tasks.length, minTime);
}
Follow Up:
1.保持顺序输出时间，thread: 1, 2, 1, 1, 3, 4; 冷却时间: 2 time slot，scheduler应该是这样的：1, 2, _, 1, _, _, 1, 3, 4，最后返回9.
["A","A","A","B","B","B"] 2，返回14
private static int taskSchedule1(int[] tasks, int cooldown) { //HashMap O(n); O(n)
if (tasks == null || tasks.length == 0) return 0;
// map: task -> 下一个task出现的时间点
HashMap<Integer, Integer> map = new HashMap<>();
int slots = 0;
for (int task : tasks) {
//if we need to wait for the cooldown of the same task, just update the slots
if (map.containsKey(task) && map.get(task) > slots) slots = map.get(task);
//update the time slot to the time when curr task can be done again
map.put(task, slots + cooldown + 1);
slots++; //important!! update the used 1 slot of current task
}
return slots;
}
2.保持顺序输出顺序 if we need to output a string of the task scheduling(without reordering), eg.1,2,1,1,3,4, k=2, -> 1 2 _ 1 _ _ 1 3 4
public static String taskSchedule2(int[] tasks, int cooldown) {
if (tasks == null || tasks.length == 0) return "";
// map: task -> 下一个task出现的时间点
Map<Integer, Integer> map = new HashMap<>();
int slots = 0;
StringBuilder sb = new StringBuilder();
for (int task : tasks) {
if (map.containsKey(task) && map.get(task) > slots) {
int waitingTime = map.get(task) - slots;
while (waitingTime-- > 0)
sb.append("#");
slots = map.get(task);
}
map.put(task, slots + cooldown + 1);
sb.append(task);
slots++;
}
return sb.toString();
}
3.不保持顺序输出顺序 output a sequence of tasks that takes least time 低频
O(maxFrequency * klogk) time, O(n) space,n is number of unique tasks
比621原题难很多。
private static String taskSchedule4(String str, int k) {
StringBuilder sb = new StringBuilder();
Map<Character, Integer> map = new HashMap<>();
for (char c : str.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((entry1, entry2) ->
entry2.getValue() - entry1.getValue());
maxHeap.addAll(map.entrySet());//O(nlogn) time, O(n) space
// 因为要一组一组加，用temp来存被展示poll下来还会被放回maxHeap的entry
ArrayList<Map.Entry<Character, Integer>> temp = new ArrayList<>();//O(k) space
while (!maxHeap.isEmpty()) {//O(max frequency) time
int i = 0;
temp.clear();
while (i <= k && !maxHeap.isEmpty()) {//O(k) time
Map.Entry<Character, Integer> entry = maxHeap.poll(); // O(lgn) time
sb.append(entry.getKey());
entry.setValue(entry.getValue() - 1);
temp.add(entry);
i++;
}
//add this code if we wanna add _ to show that we need to wait for cooldown, eg.AABB, 2 -> AB_AB
while (i <= k) {//i <= k, not i < k !!!
sb.append("_");
i++;//remember to add i++ !!!
}
// 把entry放回去
for (Map.Entry<Character, Integer> e : temp) {// O(klogk) time
if (e.getValue() > 0) {
maxHeap.offer(e);
}
}
}
//add this code if we add "_" to the string, we need to delete all the "_" at the tail, eg.A__A__ -> A__A
for (int i = sb.length() - 1; i >= 0 && sb.charAt(i) == '_'; i--) {
sb.deleteCharAt(i);
}
return sb.toString();
}
4.if cooldown is very small, but there are lots of tasks, how to reduce space to O(cooldown) space? 高频
用一个queue存cooldown waiting的queue，让map和queue都只存O(cooldown)的tasks。但map多余，不需要
private static int taskSchedule5(int[] tasks, int cooldown) { //O(n); O(cooldown)
if (tasks == null || tasks.length == 0) {
return 0;
}
Queue<Integer> queue = new LinkedList<>();//store tasks that are waiting for cooldown
HashMap<Integer, Integer> map = new HashMap<>();//store indices, where cooldown stops, of tasks in window
int slots = 0;
for (int task : tasks) {
if (map.containsKey(task) && map.get(task) > slots) {
//add this code if our output is a string, eg.AA, 2 -> A__A
//int waitingTime = map.get(task) - slots;
//for (int i = 0; i < waitingTime; i++) {
// sb.append("_");
//}
slots = map.get(task);//if we need to wait for the cooldown of the same task, just update the slots
}
if (queue.size() == cooldown + 1) {
map.remove(queue.poll());//we should do this after updating the slots, cuz we store indices of cooldown
}//stops, we don't know whether we have any idol period between these two same tasks yet, so update it first
map.put(task, slots + cooldown + 1);//update the time slot to the time when curr task can be done again
queue.offer(task);
slots++;//update the used 1 slot of curr task
}
return slots;
}
下面写法更简洁，只需要Queue，不需要map。
//queue:
//A
//A *
//A * *
//* * A
//A B *
public int leastInterval(char tasks[], int n) {
int time = 0;
Queue<Character> queue = new LinkedList<>();
for (char c : tasks) {
if (!queue.contains(c)) { //c is not in queue, exec straightly
queue.add(c);
if (queue.size() > n) { //in order to save space, must pop
queue.poll();
}
} else {
while (queue.size() <= n) { //simulate idle state, this step is necessary
queue.add('*'); //notice =, which means the size of queue is one more than cooldown time
time++;
}
while (queue.poll() != c) {
time++;
}
queue.add(c);
}
time++;
}
return time;
}