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; }