Leetcode 621. Task Scheduler

https://leetcode.com/problems/task-scheduler/description/

Notes:

Let us look at the naive way first, then we can derive a mathematics formula from the first way.

This question can be solved in a greedy way: 

         1): first we need to counts the appearance times of each letter, and then put the counts into a priority queue.

         2): from the priority queue, we cal always get the elements with the maximum count. After popping out n times, (if there are less n types of elements, we have to use idles which are as the space keeper). Then push the popped elements back to the priority queue if their counts are still larger than 0 after minus 1 (since we have used one time).

         3): we increase the total counting for every element popping (including idles)

The time complexity is about O(m*n) since we need to pop out (m*n) times any way. The priority queue also involves sorting, but there are at most 26 different kinds of letters. So this sorting can be viewed as constant.

After having this solution, we can observe one rule: the maximum counting plays one of the key important role. Since we have to run out of it anyway. If the separator is n, then we have to run (maxCount - 1) * (n + 1) units for the first (maxCount -1) letters. The last repeated process does not need to maintain at least n different letters since there is no more letter after that.

If there is only one type of letter having the maximum counting, then only one letter remaining after (maxCount - 1) time repeating. But if there are m tied maximum counting, then there will be m letters in the last repeated pattern.

So the total units are (maxCount - 1) * (n + 1) + m, where m is the letter number with tied maximum counting

Then all the rest letter can be viewed as an idle: since in each repeated pattern, we can choose one from each type. If the total units is larger than the string size, we have to use real idle as space keeper; otherwise, there is no real idle needed.

The time complexity for the second way is O(m), where m is the size of the string.

See the code below:

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int freq = 0, rep = 0;
        vector<int> ct(26, 0);
        for(auto &a : tasks) {
            ++ct[a - 'A'];
            if(freq < ct[a-'A']) {
                freq = ct[a-'A'];
                rep = 1;
            } else if (freq == ct[a-'A']) ++rep;
        }
        return max((freq - 1) * (n + 1) + rep, (int)tasks.size());
    }
};