Programmers : 디스크 컨트롤러

풀이요약

우선순위 큐

풀이상세

1. 먼저 입력값을 입력 시간 순으로 정렬한 뒤, 소요시간 순으로 오름차순 정렬을 하는 우선순위 큐를 생성한다.

2. 현재의 시간을 측정하며, 현재 시간보다 요청시간이 작거나 같은 경우에 우선순위 큐에 담아준다.

3. 디스크 컨트롤러에 작업이 다 끝나지 않았음에도, 요청시간이 현재시간보다 더 뒤에 있어 우선순위 큐에 반영되지 않는 경우도 존재할 수 있다. 이 때는 소요시간이 가장 적은 작업을 가져와 현재시간에 대입한다.

#include <vector>
#include <queue>
#include <algorithm>
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

struct cmp {
    bool operator()(pii v1, pii v2) {
        return v1.s > v2.s;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    sort(jobs.begin(), jobs.end());

    priority_queue<pii, vector<pii>, cmp> pq;
    int len = jobs.size();
    int i = 0, time = 0;
    
    while (i < len || !pq.empty()) {;
        if (i < len && jobs[i][0] <= time) {
            pq.push({jobs[i][0], jobs[i++][1]});
            continue;
        }

        if (!pq.empty()) {
            time += pq.top().s;
            answer += time - pq.top().f;
            pq.pop();
        }
        else time = jobs[i][0];
    }

    return answer / len;
}