과제 진행하기[프로그래머스]

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

struct Assignment
{
    string name;
    int startTime, playTime;
};

int NormalTime(const string& time)
{
    int hour = stoi(time.substr(0, 2));
    int minute = stoi(time.substr(3, 2));
    return hour * 60 + minute;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    sort(plans.begin(), plans.end(), [](const vector<string>& a, const vector<string>& b)
     {
        return NormalTime(a[1]) < NormalTime(b[1]);
     });
    vector<Assignment> q;
    int currentTime = 0;
    for(auto& plan : plans)
    {
        string name = plan[0];
        int start = NormalTime(plan[1]);
        int playtime = stoi(plan[2]);
        Assignment a{name, start, playtime};
        
        while(!q.empty())
        {
            Assignment& t = q.back();
            
            if(currentTime + t.playTime <= a.startTime)
            {
                currentTime += t.playTime;
                answer.push_back(t.name);
                q.pop_back();
            }
            else 
            {
                t.playTime -= (a.startTime - currentTime);
                break;
            }
        }
        q.push_back(a);
        currentTime = a.startTime;
    }
    while(!q.empty())
    {
        answer.push_back(q.back().name);
        q.pop_back();
    }
        
    return answer;
}

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

using namespace std;

struct Assignment {
    string name;
    int startTime, playTime;
    
    // 우선순위 큐(Min-Heap)를 위한 연산자 오버로딩
    // 시작 시간이 빠른 과제가 먼저 나오도록(Top에 위치하도록) 설정합니다.
    bool operator<(const Assignment& other) const {
        return startTime > other.startTime; 
    }
};

int NormalTime(const string& time) {
    int hour = stoi(time.substr(0, 2));
    int minute = stoi(time.substr(3, 2));
    return hour * 60 + minute;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    
    priority_queue<Assignment> ready_q; // 시작할 과제들 (Min-Heap)
    vector<Assignment> paused_stack;    // 멈춘 과제들 (Stack 역할)
    
    // 1. 모든 계획을 우선순위 큐에 삽입 (자동으로 시작 시간 기준 정렬 됨)
    for(auto& plan : plans) {
        ready_q.push({plan[0], NormalTime(plan[1]), stoi(plan[2])});
    }
    
    int currentTime = 0;
    
    // 2. 새로운 과제가 남아있는 동안 시뮬레이션 진행
    while(!ready_q.empty()) {
        Assignment next_task = ready_q.top();
        ready_q.pop();
        
        // 새로운 과제가 시작되기 전까지, 멈춰둔 과제들을 진행
        while(!paused_stack.empty()) {
            Assignment& paused_task = paused_stack.back();
            
            // 멈춘 과제를 끝낼 수 있는 경우
            if(currentTime + paused_task.playTime <= next_task.startTime) {
                currentTime += paused_task.playTime;
                answer.push_back(paused_task.name);
                paused_stack.pop_back();
            } 
            // 시간이 부족해 다시 멈춰야 하는 경우
            else {
                paused_task.playTime -= (next_task.startTime - currentTime);
                break; // 다음 새 과제를 시작하러 while문 탈출
            }
        }
        
        // 새로운 과제 시작 (스택에 넣고 시간 점프)
        paused_stack.push_back(next_task);
        currentTime = next_task.startTime;
    }
    
    // 3. 더 이상 남은 새 과제가 없다면, 멈춰둔 과제들을 최근 순서대로 모두 마무리
    while(!paused_stack.empty()) {
        answer.push_back(paused_stack.back().name);
        paused_stack.pop_back();
    }
    
    return answer;
}