Task Scheduler



Here is my simple Python solution, and costs 669 ms, beats 100%
What's more, it can be modified to be faster, because the sort is not necessary, and we just need to get the top two most frequent tasks.
The idea is quite simple. So I don't explain it here.
The code is as follows:class Solution(object):
def leastInterval(self, tasks, n):
"""
:type tasks: List[str]
:type n: int
:rtype: int
"""dct = {} for task in tasks: dct[task] = dct.get(task, 0) + 1 lst = dct.values() lst.sort(reverse=True) max_val = lst[0]  1 print(max_val) res = max_val*n for num in lst[1:]: if num >= max_val: res = max_val else: res = num if res < 0: return len(tasks) else: return res + len(tasks)

@zhanzq Nice solution. Thanks for sharing it. I have added your approach in the article. Thanks.

I'm confused with the time complexity of both methods. For example, in first method, aside from those operations in the inner while loop which is "time" times, you also need to sort the array for several times(this number is hard to define, but it exists, let's assume it is K), then we have another klog26. Shouldn't we consider this?

@MitchellHe when n==0, idle_slots is 0 as well, then guess what! idle_slots wille be negative after this line:"idle_slots = Math.min(map[i], max_val);" got executed

In the approach 3, you don't have to do sorting, just find the
max
value of array.public int leastInterval(char[] tasks, int n) { int[] map = new int[26]; for (char c: tasks) map[c  'A']++; int max = Integer.MIN_VALUE; for (int num : map) max = Math.max(num, max); max; int blanks = max * n + max; for (int count : map) { blanks = Math.min(count, max); } return blanks > 0 ? tasks.length + blanks : tasks.length; }

i have a solution with similar idea of 3rd solution(finding number of idels)... Disregard to the fact that my code is not clean and wellwritten at all, would someone please tell me what is the problem of this code? i get error in some of teh test cases:
public static int leastInterval(char[] tasks, int n) { if(n==0) return tasks.length; int l=tasks.length; Arrays.sort(tasks); int[] counter=new int[l]; counter[0]=1; int idx=0; for(int i=1;i<tasks.length;i++){ if(tasks[i1]!=tasks[i]){ counter[++idx]=1; } else{ counter[idx]++; } } int max=counter[0]; System.out.println(Arrays.toString(counter)); int res=(max1)*(n+1); System.out.println(idx); for(int i=0;i<=idx;i++){ int check=counter[i](max1); if(check>0){ res+=check; } } return res; }

@weisong2 note that the priority queue would have at most 26 elements inside. Insertion complexity in general case is O(log n) which in this particular task gives us O(log 26) and that decays to O(1)

The third approach does not work in all situations, as mentioned by @KeepHungry . When you have inputs like [A7, B6, C*6]and n = 1, where # of distinct tasks is greater than (n + 1) and slots created by max_value cannot hold all tasks, idle slots should grow as demand.

@KeepHungry I think you are misleading by the figure :) It's not necessary to arrange the same thread at the same column. If you arrange your test case using Approach 1, you will find that the result is actually the length of the whole input array

Here's my implementation for Approach #3, neither sorting nor the second loop is necessary. We only need to get the maximum count of a single task and how many tasks share that same number:
/** @param {character[]} tasks
 @param {number} n
 @return {number}
*/
var leastInterval = function(tasks, n) {
if(n == 0) return tasks.length;
var arr = new Array(26), max_val=0, count=1;
arr.fill(0);
for(var i=0; i<tasks.length; i++) {
var index = tasks[i].charCodeAt(0)  "A".charCodeAt(0);
arr[index]++;
if(arr[index] > max_val) {
max_val = arr[index];
count = 1;
} else if (arr[index] == max_val) count++;
}
var idle = (max_val1) * (n+1) + count;
return Math.max(idle, tasks.length);
};