Level 2. 과제 진행하기

Level 2. 과제 진행하기

 

 

우선순위 큐와 스택을 적절히 활용하는 문제다.

 

우선순위 큐는 시작 시간을 기준으로 최소힙을 구성한다.

 

다음 시작 시간 전에 과제를 끝낼 수 있으면, 현재 과제를 끝낸 후 남은 시간동안 스택에 쌓아둔 과제를 수행한다.

• 과제 시간이 부족하면 할 수 있는 만큼만 하고 스택에 쌓아둔다.

 

마지막 과제이면 해결하고 루프를 빠져나온 후, 스택에 남아있는 과제를 차례로 끝내주면 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct Plan
{
    string name;
    int start;
    int playtime;

    Plan() : name(""), start(0), playtime(0) {}

    Plan(vector<string>& plan)
    {
        name = plan[0];
        start = 60 * stoi(plan[1].substr(0, 2)) + stoi(plan[1].substr(3));
        playtime = stoi(plan[2]);
    }

    friend bool operator < (const Plan& A, const Plan& B) { return A.start > B.start; }
};

vector<string> solution(vector<vector<string>> plans)
{
    vector<string> answer;
    priority_queue<Plan> prQue;
    stack<Plan> pending;

    for (vector<string>& plan : plans)
        prQue.emplace(plan);

    while (!prQue.empty())
    {
        Plan current = prQue.top(); prQue.pop();

        if (prQue.empty())
        {
            answer.emplace_back(current.name);
            break;
        }

        int current_endtime = current.start + current.playtime;
        Plan next = prQue.top();

        if (current_endtime <= next.start)
        {
            answer.emplace_back(current.name);

            int remain = next.start - current_endtime;

            while (!pending.empty() && (0 < remain))
            {
                int t_playtime = pending.top().playtime;

                pending.top().playtime -= remain;
                remain -= t_playtime;

                if (pending.top().playtime <= 0)
                    answer.emplace_back(pending.top().name),
                    pending.pop();
            }
        }
        else
        {
            current.playtime = current_endtime - next.start;
            pending.emplace(current);
        }
    }

    while (!pending.empty())
        answer.emplace_back(pending.top().name),
        pending.pop();

    return answer;
}