1. 문제

2. 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
         // // 원본 배열 오름차순 정렬 (요청시간 오름차순)
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
        // 처리 시간 오름차순으로 정렬되는 우선순위 큐(Heap)
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        int currentTime = 0; // 수행되고난 직후의 시간
        int totalWaitTime = 0;
        int completedJobs = 0; // 수행된 요청 갯수
        int index = 0; // jobs 배열의 인덱스
        
        // 요청이 모두 수행될 때까지 반복
        while (completedJobs < jobs.length) {
            // 하나의 작업이 완료되는 시점(currentTime)까지 들어온 모든 요청을 큐에 넣음
            while (index < jobs.length && jobs[index][0] <= currentTime) {
                pq.offer(jobs[index]);
                index++;
            }
            // 작업이 끝나기 전(currentTime 이전) 들어온 요청 중 가장 수행시간이 짧은 요청부터 수행
            if (!pq.isEmpty()) {
                int[] job = pq.poll();
                currentTime += job[1];
                totalWaitTime += currentTime - job[0];
                completedJobs++;
                // (currentTime를 요청의 가장 처음으로 맞춰줌)
            } else {
                currentTime = jobs[index][0];
            }
        }
        
        return totalWaitTime / jobs.length;
    }
}

3. 풀이

• 작업 스케줄링 문제를 해결하기 위해 우선순위 큐를 사용했다. 주어진 작업들(jobs)을 요청 시간 순으로 정렬하고, 현재 시간을 기준으로 작업들을 처리했다. 작업을 우선순위 큐에 넣어 가장 작업 소요 시간이 적은 작업을 먼저 처리하도록 한다. 작업이 없는 경우에는 다음 작업의 요청 시간으로 시간을 조정한다. 작업을 처리할 때마다 대기 시간과 완료된 작업의 수를 업데이트하고, 완료된 작업의 수가 전체 작업의 수와 같아지면 반복문을 종료한다. 최종적으로 작업들의 평균 대기 시간을 구하여 반환한다.
• 주의 할 점은, 무작정 요청시간이 짧은 것으로 정렬하는게 아니라, 하나의 작업이 끝나는 시점까지 들어온 요청에 대해서 가장 짧은 수행시간을 가진 작업을 선택해야한다는 것이다 예를 들어 예시로 나온 3개의 작업에 {23, 1} 라는 배열이 하나 더 추가된다고 치면, 3개의 작업이 모두 끝날 때까지 해당 요청이 들어오지 않은 상태가 되므로 수행시간이 아무리 짧더라도 앞선 3개의 작업과 경쟁해서는 안된다.

• 람다식

 Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
 PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

 Arrays.sort(jobs, new Comparator<int[]>() {
          public int compare(int[] o1, int[] o2) {
              if(o1[0] <= o2[0]){
                  return -1;
              }
              return 1;
          }
      });      

      PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
          public int compare(int[] o1, int[] o2) {
              if(o1[1] < o2[1]){
                  return -1;
              }
              return 1;
          }
      });

4. 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42627