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

링크

코딩테스트 연습 > 힙(heap) > 디스크 컨트롤러

풀이 방법

1. jobs 정렬 (jobs가 요청시간대로 들어온다고 가정되어있지 않음)
2. '진행되고 있는 시점'기준으로 실행시간이 가장 '짧은'애를 먼저 수행

코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int count = 0; //수행한 jobs 개수
        int end = 0; //수행되고 난 직후의 시간
        int index = 0; //수행한 jobs의 인덱스
        
        //원본 배열 요청시간 오름차순 정렬
        Arrays.sort(jobs,(o1,o2) -> o1[0] - o2[0]);
        
        // 처리시간 기준 오름차순으로정렬되는 우선순위 큐 
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2) -> o1[1] - o2[1]);
        
        while(count < jobs.length){
            
            // end시점까지 실행요청들어온 jobs들을 전부 넣음 
            while((index < jobs.length) && jobs[index][0] <=end){
                pq.add(jobs[index]);
                index++;
            }
            
            if(pq.isEmpty()){
                end = jobs[index][0];
            } else{
                int[] temp = pq.poll();
                answer += temp[1] + end - temp[0];
                end += temp[1];
                count++;
            }
        }
        return answer/jobs.length;
    }
}