C++ solution (59ms)


  • 0
    S

    In order to make sure the interval, when we don't have enough different tasks to perform, we should let idle to be the "task". Therefore, we can group different tasks together, which every group meets the interval requirement.

    class Solution {
    public:
        int leastInterval(vector<char>& tasks, int n) {
            if (n == 0) return tasks.size();
            queue<char> q;
            
            vector<int> array(26, 0);
            int size = tasks.size();
            for ( int i = 0;  i < size; i++ ) {
                array[tasks[i]-'A'] += 1;
            }
            
            int count = n + 1;
            int ret = 0;
            while( size > 0 ) {
                for ( int i = 0; i < 26; i++ ) {
                    if(array[i] > 0) {
                        q.push(i+'A');
                        array[i] -= 1;
                    }
                }
                while(!q.empty() && count > 0) {
                    ret++;
                    q.pop();
                    count--;
                    size--;
                }
                while(count > 0 && size > 0) {
                    ret++;
                    count--;
                }
                count = n + 1;
            }
            
            return ret;
        }
    };
    

    The key is in the while loop. The size is the total tasks to perform. We use a queue to store different tasks. If the different tasks can not make sure the interval requirement. For example, n=2, but there are only A and B takes, we need one idle. We count the idle in the while(count > 0 && size > 0).


Log in to reply
 

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