작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법은 뭘까?

→ 3가지 작업이 있을 때, 요청은 앞에 있는 요청이 걸리는 시간만큼 기다려야 한다.

즉, 요청한 작업 중, 소요시간이 더 적게 걸리는걸 먼저 처리해야 한다!

또한 요청시점이 빠른 순서대로 우선순위 큐에 넣어야 하므로 jobs 배열을 0번째 행을 기준으로 오름차순 정렬도 해주어야 한다.

※ 우선 순위 큐에 배열 자체를 추가할 수 있다. → lamda expression 사용

• sec : 현재 시간을 나타내는 변수로 요청시점이 sec 이하의 값을 가지면 모든 원소를 큐에 추가
• idx : 현재 배열 jobs의 인덱스
• count : 수행 완료 요청 개수로 job.length 일 때 완료

따라서 sec을 기준으로 우선순위 큐에 요소를 추가하고,

→ 큐가 비어있으면 sec을 현재 확인하는 idx 요소의 요청 시점으로 이동시키고

→ 큐가 비어있지 않으면 큐에서 하나씩 빼서 “temp[1]+sec-tmp[0]”으로 시간을 계산해서 더한다.

풀이 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        **// 요청 시점이 빠른 순서대로 정렬
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
        
        // 작업 소요 시간을 기준으로 minHeap 
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> (o1[1]-o2[1]));**
        
        int sec = 0; // 현재 시점 count
        int idx = 0; // 현재 확인 idx
        int count = 0; // 수행 완료 요청 개수 -> job.length 일때 끝
        
        /* count */
        while(count < jobs.length) {
            // 배열의 idx의 요소의 시작 시점이 현재 시작 시점보다 작은 요소 put
            while(idx < jobs.length && jobs[idx][0] <= sec)
                minHeap.offer(jobs[idx++]);
                
            if(minHeap.isEmpty()) {
                // 초를 가장 빠르게 넣어야 하는 요소의 요청되는 시점으로 이동
                sec = jobs[idx][0];
            }
            else {
                int[] tmp = minHeap.poll();
                answer += tmp[1] + sec - tmp[0];
                sec += tmp[1];
                count++;
            }
        }
        
        answer /= jobs.length;
        
        return answer;
    }
}