[Leetcode] 621. Task Scheduler

1. 문제링크

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

Task Scheduler - LeetCode

 

 

 

2. key point - priority_queue를 사용하자!

1) 각 task의 횟수를 vector에 저장한다

2) 횟수가 1 이상이면 priority_queue에 push한다

3) cycle은 n + 1이다

4) queue에서 하나씩 빼서 1보다 크면 남은 횟수를 캐시해 두었다가 남은 횟수를 다시 queue에 넣어준다

 

 

 

3. solution

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> v(26, 0);
        priority_queue<int> pq;
        for(auto i : tasks){
            v[i-'A']++;
        }
        for(int i = 0; i < 26; i++){
            if(v[i] > 0)
                pq.push(v[i]);
        }
        int time = 0;
        while(!pq.empty()){
            int cycle = n + 1;
            vector<int> remain;            
            while(cycle > 0 && !pq.empty()){
                int freq = pq.top();
                pq.pop();
                if(freq > 1){
                    remain.push_back(freq-1);
                }
                cycle--;
                time++;
            }
            for(auto i : remain)
                pq.push(i);
            
            if(pq.empty())
                break;
            
            time += cycle;
        }
        return time;
    }
};