Task Scheduler

  • 0

    Click here to see the full article post

  • 0

    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

    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()
        max_val = lst[0] - 1
        res = max_val*n
        for num in lst[1:]:
            if num >= max_val:
                res -= max_val
                res -= num
        if res < 0:
            return len(tasks)
            return res + len(tasks)

  • 0

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

  • 0

    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

    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

    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

    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

    @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);
            int blanks = max * n + max;
            for (int count : map) {
                blanks -= Math.min(count, max);
            return blanks > 0 ? tasks.length + blanks : tasks.length;

  • 0

    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;
        int[] counter=new int[l];
        int idx=0;
        for(int i=1;i<tasks.length;i++){
        int max=counter[0];
        int res=(max-1)*(n+1);
       for(int i=0;i<=idx;i++){
    	   int check=counter[i]-(max-1);
       return res;

  • 0

    what is the time complexity of #2 solution? Is it O(n log n)? because the time for adding an element to priority queue is O(log n) right?

  • 0

    @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)

  • 2

    For the 3rd approach, what would happen when the input is [A *4, B *4, C 3, D 3, E *3, F *3] with n = 4? The [B, C, D, E] would occupy all the idle slots. So between tasks of 'F', there would be idle slots too. The result won't be tasks.length.

  • 0

    In Approach 3, Line 9: idle_slots -= Math.min(map[i], max_val);
    Q: why do we need a Math.min() function?

  • 0

    For approach 3, it's a very sophisticated math formula, howefver, it will be useless if a candidate came up with that solution in the interview though.

  • 0

    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.

  • 0

    @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

  • 0

    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;
      for(var i=0; i<tasks.length; i++) {
      var index = tasks[i].charCodeAt(0) - "A".charCodeAt(0);
      if(arr[index] > max_val) {
      max_val = arr[index];
      count = 1;
      } else if (arr[index] == max_val) count++;
      var idle = (max_val-1) * (n+1) + count;
      return Math.max(idle, tasks.length);

Log in to reply

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