LeetCode : 1882. Process Tasks Using Servers

 

문제)

 

0-인덱스 정수 배열 servers와 tasks가 각각 길이 n과 m으로 주어진다.

servers[i]는 i번째 서버의 가중치를 나타내고, tasks[j]는 j번째 작업을 처리하는 데 필요한 시간을 초 단위로 나타낸다.

 

작업들은 작업 큐를 사용하여 서버에 할당된다. 처음에는 모든 서버가 자유롭고 큐는 비어 있다.

 

j초에, j번째 작업이 큐에 삽입된다 (0번째 작업은 0초에 삽입된다).

자유로운 서버가 있고 큐가 비어 있지 않은 한, 큐의 맨 앞에 있는 작업이 가장 작은 가중치를 가진 자유로운 서버에 할당된다. 가중치가 같을 경우, 가장 작은 인덱스를 가진 자유로운 서버에 할당된다.

 

자유로운 서버가 없고 큐가 비어 있지 않으면, 서버가 자유로워질 때까지 기다렸다가 즉시 다음 작업을 할당한다.

 

여러 서버가 동시에 자유로워지면, 가중치와 인덱스 우선 순위에 따라 삽입 순서대로 여러 작업이 할당된다.

t초에 작업 j가 할당된 서버는 t + tasks[j]초에 다시 자유로워진다.

길이 m의 배열 ans를 만들어서, ans[j]는 j번째 작업이 할당된 서버의 인덱스를 나타내도록 한다.

 

배열 ans를 반환한다.

 

문제 난이도 : 중

 

소요시간 및 풀이)

우선 순위 큐를 이용하여 푼건 나와 동일하였다.

하지만 나는 우선 순위 큐를 하나만 이용해서 풀이를 시도했다.

그래서 주어진 서버가 일을 처리하는 중인지에 대한 상태를 제대로 관리하지 못해서 문제를 못 풀었다.

 

정답 코드 처럼 그냥 서버의 상태를 2개의 우선순위 큐로 분리해서 관리했다면 쉽게 풀 수 있었을 텐데

왜 그러지 않았는지 이해가 안간다.

 

정답 코드에서는 작업 가능한 서버와, 작업 중인 서버 두 개로 나눠서 관리한다.

처음에는 모든 서버를 free_server_pq에 넣어준다.

그 후 첫 번째 서버에 일감을 부여하고 free_server_pq에서 pop해서 busy_server_pq로 넣어준다.

while문을 돌면서 busy_server_pq가 비어있지 않고,

busy_server_pq.top().first가 time 보다 작거나 같을 경우에 => (작업중인 서버가 작업을 끝마쳤는지 확인.)

busy_server_pq에서 pop해서 다시 free_server_pq에 넣어준다.

위 과정을 반복한다.

 

소요 시간 : 못 품

 

정답 코드

class Solution 
{

public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks)
    {
        int n = servers.size();
        int m = tasks.size();

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> free_server_pq;
        priority_queue<pair<long, long>, vector<pair<long, long>>, greater<pair<long, long>>> busy_server_pq;
        vector<int> ans(m);

        for (int i = 0; i < n; ++i)
        {
            free_server_pq.push({ servers[i], i });
        }

        long time = 0;

        for (int i = 0; i < m; ++i)
        {
            time = max(static_cast<long>(i), time);

            if (free_server_pq.empty() && busy_server_pq.top().first > time) 
            {
                time = busy_server_pq.top().first;
            }

            while (!busy_server_pq.empty() && busy_server_pq.top().first <= time) 
            {
                auto& info = busy_server_pq.top();
                int server_idx = static_cast<int>(info.second);
                free_server_pq.push({ servers[server_idx], server_idx });
                busy_server_pq.pop();
            }

            auto& info = free_server_pq.top();
            busy_server_pq.push({ time + tasks[i], info.second });
            ans[i] = info.second;
            free_server_pq.pop();
        }

        return ans;
    }
};