[Programmers] 디스크 컨트롤러

[Programmers] 디스크 컨트롤러

Problem URL : 디스크 컨트롤러

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct cmp {
    bool operator()(pair<int, int>&a, pair<int, int>&b) {
        if (a.second == b.second) {
            return a.first > b.first;
        }else {
            return a.second > b.second;
        }
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>, cmp> pq;
    // 작업이 요청되는 시점이 작은 순으로, 같으면 작업의 소요시간이 작은 순으로 정렬
    sort(jobs.begin(),jobs.end());
    int t = jobs[0][0];
    int sum = 0;
    pq.push({jobs[0][0], jobs[0][1]});
    int idx = 1;
    int size = jobs.size();
    int popNum = 0;
    while(popNum != size) {
      if(pq.empty()) {
        // 작업할게 없을 때, 요청되는 시점이 제일 빠르고, 소요시간이 제일 적은 작업을 큐에 넣는다.
        pq.push({jobs[idx][0],jobs[idx][1]});
        t = jobs[idx][0];
      }else {
        t += pq.top().second;
        sum += t - pq.top().first;
        pq.pop();
        popNum++;
        while(idx < size && jobs[idx][0] <= t) {
          pq.push({jobs[idx][0], jobs[idx][1]});
          idx++;
        }
      }
    }

    answer = sum / size;
    return answer;
}