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

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

프로그래머스

 
먼저, 모든 작업을 처리한, 총 ms를 구한다.
(기저사항, 모든 작업이 끝났는지 확인하기 위함)
 
요청은 무조건 먼저 들어오는 순으로 받아야 하기 때문에, 요청 시간을 기준으로 오름차순으로 정렬한다.

현재 시간과 현재 처리 중인 요청을 저장할 변수를 선언한다.

더 처리할 요청이 남아있고, 현재 시간에 요청이 있을 경우, 큐에 { 수행 시간, 요청 시간 }으로 넣는다.

이러면, 새 데이터가 들어오면 우선순위 큐에서 수행 시간을 기준으로 오름차순으로 정렬하여, 새 작업을 선택할 때마다, 현재 작업 요청이 들어와 있는 애들 중, 가장 수행 시간이 짧은 요청을 수행한다.

요청 수행은 기본적인 해당 요청을 처리하는 데 걸리는 시간 + 요청한 시점으로부터 지금까지 걸린 시간를 답에 더한다.

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

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 오름차순

int solution(vector<vector<int>> jobs) {
	int Answer = 0, End = 0;
	sort(jobs.begin(), jobs.end()); // 오름차순 정렬

	// 모든 작업이 끝나는 시간
	for (const auto& job : jobs)
	{
		End = max(End, job[0]);
		End += job[1];
	}

	// 현재 시간, 처리된 요청
	int ms = 0, Index = 0;
	while (ms < End)
	{
		// 처리된 요청이 모두 대기중인 경우, 아직 요청할 시간이 아닌 경우
		while (Index < jobs.size() && jobs[Index][0] <= ms)
		{
			// { 시간, 요청 } 순서로 우선순위 큐에 저장 (걸리는 시간이 짧은 순서대로 오름차순 정렬됨)
			pq.push({ jobs[Index][1], jobs[Index][0] });
			Index++;
		}

		if (!pq.empty())
		{
			// 요청을 처리하는 데 걸리는 시간 + 요청한 시점으로부터 현재 시간까지 대기한 시간
			Answer += pq.top().first + (ms - pq.top().second);
			ms += pq.top().first; // 한 번에 한 가지 요청만 처리할 수 있기 떄문에, 걸리는 시간만큼 더함
			pq.pop();
		}
		else ms++;
	}
	return Answer / jobs.size();
}