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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

---

C++ 풀이

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct cmp {
	bool operator()(vector<int> a, vector<int> b) {
		return a[1] > b[1]; //짧은 작업 시간 우선
	}
};

int solution(vector<vector<int>> jobs) {
	sort(jobs.begin(), jobs.end());
	priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
	vector <int> temp;
	int current_time = 0;
	int time_sum = 0;
	int index = 0;
	int jobsLeft = jobs.size();
	while (jobsLeft > 0) {
		while ((index < jobs.size()) && (jobs[index][0] <= current_time)) {
			pq.push(jobs[index]); //현 시점에서 시작 가능한 작업들만 우선순위 큐에 삽입
			index++;
		}
		if (!pq.empty()) {
			temp = pq.top();
			if (temp[0] <= current_time) {
				time_sum += (current_time - temp[0]) + temp[1];
				pq.pop();
				jobsLeft--;
				current_time += temp[1];
			}
			else {
				current_time = temp[0];
			}
		}
		else { //시작 가능한 작업이 없을 경우, 시간 증가
			current_time++;
		}
	}
	return (time_sum / jobs.size());
}

우선순위 큐를 사용하여 풀었다.

현 시점에서 처리 가능한 작업들 중, 가장 소요시간이 짧은 작업을 우선으로 처리하도록 구현하였다.