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

풀이:

우선순위 큐를 이용해서 힙정렬 !

그런데 큐에 요청시간과 작업시간을 넣을때 요청시간이 같은것은 한번에 다 넣어줘야

작업시간이 짧은 순으로 차례대로 제대로 작동 시킬수 있다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct comp{
  bool operator() (const pair<int,int> &a, const pair<int,int> &b){
      return a.second>b.second;
  }  
};
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue< pair<int,int> , vector<pair<int,int> > , greater<pair<int,int>> > q;
    priority_queue< pair<int,int> , vector<pair<int,int> > , comp > work;
    for( auto i : jobs){
        q.push(make_pair(i[0],i[1]));
    }
    if(work.empty()){
        work.push(q.top());
        q.pop();
        while(!q.empty()&&work.top().first == q.top().first){
             work.push(q.top());
             q.pop();
        }
    }
    int t =work.top().first;
    while(!work.empty()){
        pair<int,int> now =work.top();

        work.pop();
        t+= now.second;
        //cout<<now.first<<" "<<now.second<<" "<<t<<" "<<t-now.first<<endl;
        answer += t - now.first;
        while(!q.empty()&&q.top().first<=t){
            work.push(q.top());
            q.pop();
        }
        if(work.empty()&&!q.empty()){
            work.push(q.top());
            q.pop();
            t = work.top().first;
            while(!q.empty()&& t == q.top().first){
                work.push(q.top());
                q.pop();
            }
        }
    }
    return answer/jobs.size();
}

 

* 구조체를 이용해서 우선순위 큐의 정렬 방식을 구현할수있다