621. Task Scheduler

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> v(26);
        int freq = 0;
        for (auto c : tasks)
            freq = max(++v[c - 'A'], freq);
        
        int count = 0;
        for (int i = 0; i < v.size(); ++i)
            if (v[i] == freq) count++;
        
        int with_idle = (n + 1) * (freq - 1) + count;
        int no_idle = tasks.size();
        return max(with_idle, no_idle);
    }
};

max frequency tasks를 제외한 tasks에 대해,

- (n + 1) 슬롯에서의 idle time을 채우거나 남는다면 : tasks.size

- idle time을 채우지 못한다면 : (n + 1) * (freq - 1) + count

 

(priority_queue를 활용한 greedy 방식이 일반적인 풀이)