[PGS / Heap] 디스크 컨트롤러 (java)

문제 보기

소요 시간

문제

하드디스크는 한 번에 하나의 작업만 수행 가능, 디스크 컨트롤러를 구현하는 방법은 여러가지가 있다.

• 입력: [작업 요청 시점, 작업의 소요시간]을 담은 2차원 배열 jobs
  (1 <= jobs.length <= 500)
• 출력 : 작업의 요청부터 종료까지 걸린 시간의 평균 최솟값
  
  
• 각 작업에 대한 작업 소요시간은 1이상 1000 이하이다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리한다.

문제풀이

소요시간이 작은 것을 먼저 처리해야 작업 처리 소요시간이 줄어든다.
따라서, 현재 시점보다 작은 요청 시점들의 작업들을 소요 시간이 작은 순의 힙에 추가하고, 가장 소요 시간이 짧은 작업부터 실행한다.

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

class Solution {
    public int solution(int[][] jobs) {
        int now = 0; // 현재 시간
        int cnt = 0; // 수행된 작업 수
        int idx = 0; // jobs 인덱스
        int time = 0;

        Arrays.sort(jobs,(o1, o2) -> o1[0]-o2[0]); // 요청시간 오름차순
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1,o2) -> o1[1]-o2[1]); // 처리시간 오름차순
        while (cnt < jobs.length){
            while(idx < jobs.length && now >= jobs[idx][0]) minHeap.add(jobs[idx++]);
            if(minHeap.isEmpty()) now = jobs[idx][0];
            else {
                now += minHeap.peek()[1];
                time += (now - minHeap.peek()[0]);
                minHeap.poll();
                cnt++;
            }
        }
        time /= jobs.length;
        return time;
    }
}

성능 검사

O(N^2)