leetcode 621. Task Scheduler
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].
下面是我的解法：theTasks里包含26个大写字母的tasks次数。需要注意的是 之后有对数组进行排序，所以theTasks[0]不一定对应着'A'，其余也不一定对应。我们这一题并不需要关心是否字母对应，只关心从大到小的数字。
package leetcode;
public class Task_Scheduler_621 {
public int leastInterval(char[] tasks, int n) {
int[] theTasks=new int[26];
int[] needRest=new int[26];
int num=tasks.length;
for(int i=0;i<num;i++){
theTasks[tasks[i]-'A']++;
}
sortDesc(theTasks, needRest, 0, 25);
int result=0;
while(num>0){
boolean findTaskToDo=false;
int i=0;
for(i=0;i<26;i++){
if(theTasks[i]>0&&needRest[i]==0){
findTaskToDo=true;
theTasks[i]--;
needRest[i]=n;
num--;
break;
}
}
result++;
for(int j=0;j<26;j++){
if(j!=i&&needRest[j]>0){
needRest[j]--;
}
}
if(findTaskToDo==true){
sortDesc(theTasks, needRest, 0, 25);
}
}
return result;
}
public void sortDesc(int[] tasks,int[] needRest,int left,int right){
if(left<right){
int low=left;
int high=right;
int pivot=tasks[low];
int pivot2=needRest[low];
while(low<high){
while(low<high&&tasks[high]<=pivot){
high--;
}
tasks[low]=tasks[high];
needRest[low]=needRest[high];
while(low<high&&tasks[low]>=pivot){
low++;
}
tasks[high]=tasks[low];
needRest[high]=needRest[low];
}
tasks[low]=pivot;
needRest[low]=pivot2;
sortDesc(tasks, needRest, left, low-1);
sortDesc(tasks, needRest, low+1, right);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Task_Scheduler_621 t=new Task_Scheduler_621();
char[] tasks=new char[]{'A','B','B'};
int n=2;
System.out.println(t.leastInterval(tasks, n));
}
}Solution
Approach #1 Using Sorting [Accepted]
使用map数组来储存每个任务的次数。然后，我们根据次数从大到小的顺序来执行任务。每次取前n+1个tasks来执行。如果前n+1个tasks存在，则执行完一个，time就+1。如果前n+1个tasks不存在，即当前剩下的tasks已经小于n+1了，那么还是time+1，这是 idle使得time+1。再次循环前n+1个tasks时，这前n+1个tasks一定是已经休息完了的状态。
Now, the task picked up first after the sorting, will either be the first task picked up in the last iteration(which will now be picked after its cooling time has been finished) or the task picked will be the one which lies at (n+1)th position in the previous descending tasks array. In either of the cases, the cooling time won't cause any conflicts(it has been considered implicitly). Further, the task most critical currently will always be picked up which was the main requirement.
Java
public class Solution { public int leastInterval(char[] tasks, int n) { int[] map = new int[26]; for (char c: tasks) 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; } }
Complexity Analysis
-
Time complexity : O(time). Number of iterations will be equal to resultant time time.
-
Space complexity : O(1). Constant size array map is used.
Approach #2 Using Priority-Queue [Accepted]
Algorithm
使用一个最大堆(优先级队列)，来代替上面方法中 每循环一次都要排序。
我们首先把元素放入map中计算count，再把 >0 的次数放入queue 中。然后，我们开始 pop 出queue 中次数最大的任务，然后执行它，减少它的次数，如果它的次数还大于0，那么将它存入一个暂时的temp数组（用来之后再次存入queue）。然后继续做这件事，直到做了n+1次为止（这样一个冷却时间回合已经结束了）。在每次回合之后，我们把 temp 数组中的元素重新放入 queue 。
Java
public class Solution { public int leastInterval(char[] tasks, int n) { int[] map = new int[26]; for (char c: tasks) map[c - 'A']++; PriorityQueue < Integer > queue = new PriorityQueue < > (26, Collections.reverseOrder()); for (int f: map) { if (f > 0) queue.add(f); } int time = 0; while (!queue.isEmpty()) { int i = 0; List < Integer > temp = new ArrayList < > (); while (i <= n) { if (!queue.isEmpty()) { if (queue.peek() > 1) temp.add(queue.poll() - 1); else queue.poll(); } time++; if (queue.isEmpty() && temp.size() == 0) break; i++; } for (int l: temp) queue.add(l); } return time; } }
Complexity Analysis
-
Time complexity : O(n). Number of iterations will be equal to resultant time time.
-
Space complexity : O(1). queue and temp size will not exceed O(26).
Approach #3 Calculating Idle slots [Accepted]
Algorithm
如果我们能够知道idle的次数，我们就能知道最终执行的时间。最终执行时间= idle_次数+任务的总个数.
首先看图1：
从图1中可以看出，idle的最大数取决于 (次数最大的任务的次数-1) * 每次的冷却时间 。而idle次数的减少则取决于其他任务的次数。
Java
public class Solution { public int leastInterval(char[] tasks, int n) { int[] map = new int[26]; for (char c: tasks) map[c - 'A']++; Arrays.sort(map); int max_val = map[25] - 1, idle_slots = max_val * n; for (int i = 24; i >= 0 && map[i] > 0; i--) { idle_slots -= Math.min(map[i], max_val); } return idle_slots > 0 ? idle_slots + tasks.length : tasks.length; } }
Complexity Analysis
-
Time complexity : O(n). We iterate over tasks array only once. (O(n)).Sorting tasks array of length n takes O(26log(26))=O(1) time. After this, only one iteration over 26 elements of map is done(O(1).
-
Space complexity : O(1). map array of constant size(26) is used.
Examples:
AAAABBBEEFFGG 3
here X represents a space gap:
Frame: "AXXXAXXXAXXXA"
insert 'B': "ABXXABXXABXXA" <--- 'B' has higher frequency than the other characters, insert it first.
insert 'E': "ABEXABEXABXXA"
insert 'F': "ABEFABEXABFXA" <--- each time try to fill the k-1 gaps as full or evenly as possible.
insert 'G': "ABEFABEGABFGA"
推荐阅读