[프로그래머스] 42627. 디스크 컨트롤러

문제 링크

[프로그래머스] 42627. 디스크 컨트롤러

풀이 과정

운영체제의 SJF(Shortest Job First) 알고리즘을 따르면 각 작업의 대기부터 처리까지의 시간 이 최소가 됩니다.

한 작업의 처리가 끝났을 때, 그 시점에 기다리고 있는 작업들을 모두 우선순위 큐에 넣어준 다음, 소요 시간이 짧은 작업부터 처리하면 문제를 해결할 수 있습니다.

코드

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

public class Main {
    public static int solution(int[][] jobs) {
        int answer = 0;
        int end = 0;
        int cnt = 0;
        int idx = 0;

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

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

        while (cnt < jobs.length) {
            while (idx < jobs.length && jobs[idx][0] <= end) {
                pq.add(jobs[idx++]);
            }

            if (pq.isEmpty()) {
                end = jobs[idx][0];
            } else {
                int[] now = pq.poll();
                answer += end + now[1] - now[0];
                end += now[1];
                cnt++;
            }
        }

        return (int) Math.floor(answer / jobs.length);
    }

    public static void main(String[] args) {
        int[][] jobs = {{0, 3}, {1, 9}, {2, 6}};

        solution(jobs);
    }
}