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

풀이 

현재 시각 기준에서 작업시간이 제일 작은것을 수행하는 것이 총 수행시간에서 이득이다.

 

1.우선순위큐를 통해 업무시간, 시작시간 순으로 정렬한다.

2. 현재시각에서 처리할수 있는 작업이라면 처리한다.

3.현재 시각에서 처리할 수 없는 작업이라면 다른 큐에 넣어준다.

4. 모든 큐를 검토했을때 시작할 수 있는 큐가 없다면 시간을 +1 해준다.

5.  2 이후에 for문을 나왔다면 다른큐에 있던 작업들을 원래 큐에 다시 담아준다. 

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

using namespace std;


//현재 실행할 수 있는 작업중에 제일 업무시간이 작은 작업을 수행한다. 
//1. 업무시간 순으로 정렬 
//2. 현재 시간과 비교
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q2;
int solution(vector<vector<int>> jobs) {
    int answer = 0;

    int time=0;
    //소요시간 순으로 정렬 {작업 소요시간, 작업 요청 시점}
    for(auto j : jobs){
        q.push({j[1],j[0]});
    }
    
    while(!q.empty()){
        for(int i=0;i<q.size();i++){
            if(q.top().second<=time){
                time+=q.top().first;
                answer+=(time-q.top().second);
              //  cout<<answer<<endl;
                q.pop();
        
                break;
            }
            else{
                q2.push(q.top());
                q.pop();
                i--;
            }
           
            if(i==q.size()-1)time++;
        }
        while(!q2.empty()){
            q.push(q2.top());
            q2.pop();
        }
    }

    return answer/jobs.size();
}