Java O(n) solution beats 99.76%, use only array, easy understanding


  • 3
    C

    There is one crucial point for you:
    the ONLY thing you need to care is the max number of one task!
    We set apart each max task with interval n, and we hope to put all other tasks into those intervals. If the number of those tasks exceeds the interval space, then we don't need any idle interval at all. If not, the interval space plus the max tasks will be the least interval. Be care for the existent of multiple max tasks.

    public class Solution {
        public int leastInterval(char[] tasks, int n) {
            int[] storage = new int[26];
            for (char c : tasks) {
                storage[(c - 'A')]++;
            }
            int max = 0;
            int count = 1;
            for (int num : storage) {
                if (num == 0) {
                    continue;
                }
                if (max < num) {
                    max = num;
                    count = 1;
                } else if (max == num) {
                    count++;
                }
            }
            int space = (n + 1) * (max - 1) + count;
            return (space < nums.length) ? nums.length : space;
        }
    }
    

Log in to reply
 

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