621. Task Scheduler

Problem description:

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:
Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

Solution:

1. count max frequency
2. find how many tasks are max frequency
3. calculate the scheduled slots by max frequency. The idea here is we assume the tasks list is max_frequency tasks dominant
4. If the scheduled slots is smaller than len(tasks), it means there’re enough tasks to fill out the cooldown interval.

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if n == 0:
            return len(tasks)
        
        count = Counter(tasks)
        max_freq = max(count.values())
        num_max_freq = sum(1 for task, freq in count.items() if freq == max_freq)
        
        scheduled = (max_freq -1) * (n+1) + num_max_freq
        return max(len(tasks), scheduled)

Solution: Heap

The idea is to find the largest frequency element in the heap, schedule it in a round, then put it aside in a tmp (to not schedule it before cooldown time).

If one of the round we have no task in heap and nothing in tmp , it means no remaining task, no need to continue.

Otherwise, if no task in heap but have task in tmp, it means we have to wait for cooldown.

When end of a round, push the tasks in tmp back to heap for next round.

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        heap = [(-v, k) for k, v in count.items()]
        heapify(heap)
        
        res = 0
        while heap:
            i = 0
            tmp = []
            while i <= n:
                if heap:
                    v, k = heappop(heap)
                    if -v > 1:
                        tmp.append((v+1, k))
                res += 1
                
                # all elements has been pop out from heap
                # but they still have remain taks keeping in tmp
                if not heap and not tmp: 
                    break
                i += 1
            
            # end of a round, put the task back to heap
            for task in tmp:
                heappush(heap, task)
        return res

Solution:

The idea is to count whether if we need extra idle slots.

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> map(26, 0); //only 26 character
        for (auto c: tasks) 
            map[c - 'A']++; //count which task has the largest frequency
        
        sort(map.begin(), map.end());
        
        int max_val = map[25] - 1; //last element do not need cool down
        int idle_slots = max_val * n;
        for (int i = 24; i >= 0 && map[i] > 0; i--) { 
            //already set up the largest one, so start at i=24
            idle_slots -= min(map[i], max_val);
        }
        //if idle slot > 0, some of the task need extra. 
        //idle slot < 0, don't need idle slots
        return idle_slots > 0 ? idle_slots + tasks.size() : tasks.size();
    }
};

Second time

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        /*
        idea: count how many extra idle slot needed.
        1. count which task will be the most.
        2. the last task do not need idle slot, so remember to deduct 1
        */
        
        map<int, int> map;
        
        for(auto c: tasks){
            map[c-'A']++;
        }
        
        vector<int> after;
        for(auto m: map){
            after.push_back(m.second);
        }
        
        sort(after.begin(), after.end());
        int max_val= after[after.size()-1]-1;
        int idle_slot= n* max_val;
        
        
        for(int i= after.size()-2; i>= 0; i--){
            idle_slot-= min(after[i], max_val);
        }
        
        return idle_slot < 0? tasks.size(): idle_slot+tasks.size();
        
    }
};

Third time:

Use a vector to count every appeared character.
Sort the vector, it will be ascending order; therefore, the largest element would be in the last.

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> count(26, 0);
        for(auto c: tasks)
            count[c-'A']++;
            
        sort(count.begin(), count.end());
        int idle= n* (count[25]-1);
        
        for(int i= 24; i>= 0; i--){
            idle-= min(count[i], count[25]-1);
        }
        
        return idle>0 ? tasks.size()+idle: tasks.size();
    }
};

reference:
https://goo.gl/DaFYrA
https://goo.gl/unPm4P
https://goo.gl/JhFQuh