Solution.java

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        Arrays.sort(jobs, Comparator.comparingInt(o -> o[0]));
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i = 0, time = 0, run = 0; i < jobs.length || !pq.isEmpty(); time++, run--) {
            answer += pq.size();
            
            while (i < jobs.length && jobs[i][0] == time) {
                pq.add(jobs[i][1]);
                i++;
            }
            
            if (run <= 0 && !pq.isEmpty()) {
                run = pq.poll();
                answer += run;
            }
        }
        
        answer /= jobs.length;
        
        return answer;
    }
}

우선순위 큐를 이용하면 쉽게 풀 수 있는 문제였다.

컴퓨터구조 수업이었나 전공 수업에서 이 문제와 비슷한 이론을 배웠던 기억이 나서 더 쉽게 풀었던 것 같다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges