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

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

코딩테스트 연습 - 디스크 컨트롤러

우선순위 힙을 이용해 풀이

참조 : https://codevang.tistory.com/316

프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA)

package level3;

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

	
	/******************************************************
	 * ① 요청시간 순서대로 데이터를 정렬
	 *   >> 처리시간이 작은 작업부터 수행해야 전체 수행시간 평균치가 작을 것이라 예상	    
	 * ② 우선순위큐(힙) : 가장 작은 시간을 꺼내는데 최소힙을 사용
	 * ③ ①,②를 통해 정렬된 순서대로 작업을 수행 
	 ******************************************************/
     
public int solution(int[][] jobs) {
		
	//① 작업요청시간 순서대로 정렬		
	Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
	
	//② 처리시간 순서대로 우선순위큐(최소힙)
	PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
	int start = 0; // 작업이 시작이 가능한 시점을 저장
	int answer = 0;
	int count = 0; //처리한 작업의 갯수 
	int jobIndex = 0; //작업 Index
		
	while(count < jobs.length) {
			
		//작업 요청 시간이 작업시작가능시점보다 작거나 같으면 모두 작업 Queue에 저장
		while( jobIndex<jobs.length && jobs[jobIndex][0]<=start) {
            
			pq.add(jobs[jobIndex++]);				
			
		}			
		//작업이 비어있으면, 작업이 시작될 시점을 저장
		if(pq.isEmpty()) {
			
			start = jobs[jobIndex][0];
			
		}else {
                  //작업 수행	
                  int[] j = pq.poll();
                  int requestTime = j[0];
                  int runningTime = j[1];

                  answer += start+runningTime-requestTime; //작업시작시점 + 작업시간 - 요청시간

                  start += runningTime;//작업시작시점 = 작업시작시점 + 작업수행시간

                  count++; //처리한 작업의 갯수 증가
		}			
	}
		return answer/jobs.length;
}