[LeetCode] 621. Task Scheduler

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

Leetcode - Task Scheduler

문제 유형 : 그리디, 정렬

문제 난이도 : Medium

 

문제

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

 

문자 A-Z로 이루어진 tasks 배열이 주어진다. 쿨링 타임 n이 주어진다.

같은 문자의 작업을 시행하는 데에는 n의 간격이 필요하다.

모든 작업을 실행하는 최소 시간을 구하시오.

 

풀이

배열에 문자의 빈도를 저장시킨다.

정렬하고, (가장 큰 값의 빈도-1) * n으로, 각각의 문자별로 인터벌을 가져야한다는 의미로, 기본 추가 인터벌을 정한다.

다른 문자를 처리하는 경우를 생각하지 않고 무작정 작업을 하였을 때 더 기다리는 수치이다.

 

배열을 순차적으로 순회하면서, 기본 휴식시간에서 min(가장 큰 값의 빈도 -1, 현재 요소의 빈도)만큼 빼준다.

다른 문자의 작업을 처리하면서, 더 기다릴 필요가 없는 만큼 빼는 것이다.

 

기다리는 값이 음수가 되면, 기다릴 필요가 없다는 뜻으로, tasks의 크기를 반환하면 되고,

아니라면, tasks의 크기에 기다리는 값을 더해서 반환한다.

 

코드

C++

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> freq(26, 0);

        for(auto task : tasks) {
            freq[task - 'A']++;
        }

        sort(freq.begin(), freq.end());

        int most = freq[25] - 1;
        int idle = most * n;

        for(int i = 24; i >= 0; i--) {
            idle -= min(most, freq[i]);
        }

        return idle < 0? tasks.size() : tasks.size() + idle;
    }
};