[프로그래머스] 디스크 컨트롤러

[프로그래머스] 디스크 컨트롤러

문제 링크

#include "header.h"
using namespace std;
int visit[1001];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

bool cmp(vector<int> a, vector<int>b){
    if(a[0] >= b[0]){
        if(a[0] == b[0]){
            if(a[1] < b[1]){
                return true;
            }
            return false;
        }
        return false;
    }
    return true;
}
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int total_time = 0;

    sort(jobs.begin(), jobs.end(), cmp);

    pq.push({jobs[0][1], jobs[0][0]}); //맨 처음에 넣기
    visit[0] = 1;

    while(!pq.empty()){
        int top_start = pq.top().second;
        int top_duration = pq.top().first;

        if(top_start > total_time){
            total_time += top_start;
        }
        
        total_time += top_duration;
        answer += total_time - top_start;
        
        pq.pop();

        for(int i=1; i<jobs.size(); i++){
            if(visit[i]) continue;
            int start = jobs[i][0];
            int duration = jobs[i][1];

            if(start <= total_time){ //신청 기간이 지났음
                pq.push({jobs[i][1], jobs[i][0]});
                visit[i] = 1;
            }
        }
    }


    for(int i=0; i<jobs.size(); i++){
        if(!visit[i])
            answer += (jobs[i][0] - total_time) + jobs[i][1];
    }


    return answer / jobs.size();
}

• 최대한 빨리 끝낼 수 있는 애를 골라야 함 -> duration이 제일 적은 애 -> priority queue로 작업
• 대신 대기 시간도 더해주어야 함.
• 0-3 => 3
• 2-6 => 9에 끝남, (3-2) 1만큼 대기 ==> 9-2 = 7만큼 걸림
• 1-9 => 18에 끝남, (9-1) 8만큼 대기 ==> 18-1 = 17만큼 걸림

• total_time(걸린 시간) - start(시작 시간)

• 제일 빠른 순으로 정렬 해 주고, 시작시간이 아직 되지 않았을 경우 (top_start > total_time) 예외 처리후 pop해 더해준다.
• 우선순위 큐가 빈 후에, 시간이 늦어 아직 작업 큐에 들어가지 않은 애들도 처리 해 준다.