Task Scheduler


  • 0

    Click here to see the full article post


  • 0
    J

    In the approach 1, I think instead of

    if (map[25] == 0 && map[25 - i] == 0)

    This would suffice

    if (map[25] == 0)


  • 0

    @JkApacc Thanks for your suggestion. I have updated the code.


  • 0
    Z

    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)

  • 0

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


  • 0
    D

    sort make it easier to understand. But actually all we need is to find out the biggest number in the map, just a linear scan would be sufficient.


  • 0
    A

    i think PriorityQueue solution is just as same as Sort solution since we insert element one by one into the queue, it's just a heap-sort..


  • 0
    F

    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?


  • 0
    M

    For the last solution, there is a condition idle_slots > 0 in the line of return. I guess it was because idle_slots might be negative. Am I right? If yes, why could idle_slots be negative?


  • 0
    L

    @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


  • 0

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

  • 0
    C

    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 well-written 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[i-1]!=tasks[i]){
                counter[++idx]=1;
            }
            else{
                counter[idx]++;
            }
        }
    
        
        int max=counter[0];
        System.out.println(Arrays.toString(counter));
        int res=(max-1)*(n+1);
        System.out.println(idx);
       for(int i=0;i<=idx;i++){
    	   int check=counter[i]-(max-1);
    	   if(check>0){
    		   res+=check;
    	   }
       }
       return res;
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.