Lv 3. 디스크 컨트롤러

 

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

프로그래머스

 

 

 

이 문제는  주어진 작업들의 평균 대기 시간을 최소화하는 문제다.

jobs 배열은 각 작업의 요청 시간과 소요 시간을 담고 있으며,

이를 효율적으로 처리하기 위해 힙(우선순위 큐)을 사용한다.

 

먼저 jobs 배열을 요청 시간 기준으로 오름차순 정렬해

작업이 들어온 순서대로 처리할 수 있게 한다.

작업 대기 시간을 최소화하려면 요청된 작업 중 소요 시간이 짧은 작업을

우선 처리하는 것이 좋으므로,

우선순위 큐에 각 작업을 소요 시간 기준으로 넣고 꺼내면서 처리한다.

 

반복문에서는 end가 현재 시간 역할을 하며, 요청 시간이 end 이하인 작업을 큐에 추가한다.

만약 큐가 비어 있다면,

다음 작업의 요청 시간으로 end를 갱신해 대기 시간을 최소화한다.

큐에 작업이 있을 경우,

소요 시간이 짧은 작업을 꺼내 answer에 대기 시간과 소요 시간을 합산해 누적하고,

end를 해당 작업이 끝난 시간으로 갱신한다.

 

최종적으로 모든 작업을 처리한 후

answer를 작업 수로 나눈 평균을 반환해 평균 대기 시간을 구한다.

 

 

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
	public int solution(int[][] jobs) {
		int answer = 0;
		int end = 0; 
		int idx = 0; 
		int count = 0; 
		Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
		while (count < jobs.length) {
			while (idx < jobs.length && jobs[idx][0] <= end) {
				pq.add(jobs[idx++]);
			}
            if (pq.isEmpty()) {
				end = jobs[idx][0];
			} else {
				int[] node = pq.poll();
				answer += node[1] + end - node[0];
				end += node[1];
				count++;
			}
		}
		return (int) Math.floor(answer / jobs.length);
	}
}