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

문제

---

풀이 (2021.08.26)

처리 규칙은 2가지다.

1. REQUEST가 먼저 들어온 순서로 처리한다.
2. 하나의 REQUEST를 완료했을 때 대기열에 들어 있는 작업들 중 DURATION이 가장 짧은 것을 처리한다.

구현은 jobs를 REQUEST 오름차순 순으로 정렬하고,
작업 하나를 처리완료한 시점에 PriorityQueue에 DURATION 오름차순 순으로 다음 작업들을 집어 넣는 방식으로 했다.

코드

import java.util.*;

class Solution {
    private static final int REQUEST = 0;
    private static final int DURATION = 1;
    
    public int solution(int[][] jobs) {
        int jobCount = jobs.length;
        Arrays.sort(jobs, (o1, o2) -> o1[REQUEST] - o2[REQUEST]);
        
        int finishedCount = 0;
        int queued = 0;
        int time = 0;
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (o1, o2) -> jobs[o1][DURATION] - jobs[o2][DURATION]
        );
        
        while (finishedCount < jobCount) {
            while (queued < jobCount) {
                if (jobs[queued][REQUEST] > time) {
                    break;
                }
                pq.offer(queued++);
            }
            
            if (pq.isEmpty()) {
                time = jobs[queued][REQUEST];
                pq.offer(queued++);
                continue;
            }
            
            int working = pq.poll();
            answer += time - jobs[working][REQUEST] + jobs[working][DURATION];
            time += jobs[working][DURATION];
            finishedCount++;
        }
        
        return answer / jobCount;
    }
}