11ms Java with exlaination. Pretty like a math problem


  • 0
    S

    We can just imagine there N buckets while N the max number of certain task. We iteratively put tasks into these buckets.
    The trick is when there are N same tasks for A, then one A will be put into one bucket. For those tasks whose number is less than N, just go iteratively from the first bucket to the N - 1 bucket.
    Here is the solution

    public int leastInterval(char[] tasks, int n) {
            int[] count = new int[26];
            for(char c : tasks) count[c - 'A']++;
            Arrays.sort(count);
            int max = count[25];
            if(max == 1) return tasks.length;
            int sum = 0;
            int i = 25;
            while(i >= 0 && count[i] == max) i--;
            for(int j = 0; j <= i; j++) sum += count[j];
            if(sum == 0) return n + 1 > tasks.length / max ? (n + 1) * (max - 1) + (tasks.length / max) : tasks.length;
            int layers = sum / (max - 1);
            if(layers + 25 - i < n + 1)
                return (n + 1) * (max - 1) + 25 - i;
            return sum + (25 - i) * max;
        }
    

Log in to reply
 

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