[Programmers/Java] 디스크 컨트롤러

문제

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

프로그래머스

풀이

스케쥴링 기법 중 SJF(Shortest Job First)에서 아이디어를 얻어와 문제를 해결했다.

Shortest Job First란, 수행해야할 Job 중에 가장 수행 시간이 짧은 Job을 먼저 수행하여 convoy effect(https://www.geeksforgeeks.org/convoy-effect-operating-systems/)를 방지하는 스케쥴링 기법이다.

이 문제에서는 수행해야할 Job의 도착 시간이 주어지기 때문에 다음과 같이 시뮬레이션하여 문제를 해결하였다.

1. 수행할 Job들을 시작 시간을 기준으로 오름차순 정렬한다.
2. 이후, 수행 시간을 기준으로 오름차순하는 우선순위 큐를 선언한다.
3. 현재 수행 가능한 모든 Job을 확인한다. 수행 가능한 Job이 없으면 수행까지 가장 시간이 적게 남은 Job의 시작 시간으로 현재 시간을 증가시키고 3번을 반복한다.
4. 수행 가능한 모든 Job 중 우선순위가 높은 것 부터 수행하며 대기시간을 계산한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        // 시작 순서를 기준으로 오름차순
        Arrays.sort(jobs, (o1, o2) -> Integer.compare(o1[0], o2[0]));

        // 소요 시간 기준으로 오름차순
        PriorityQueue<int[]> executablePriorityQueue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));

        int waitTime = 0; // 모든 job들의 대기 시간
        int endTime = jobs[0][0]; // 가장 최근의 job이 끝난 시간
        int jobIndex = 0;
        int executedCnt = 0; // 수행된 job 카운터

        while (executedCnt < jobs.length) {
            // endTime보다 같거나 작은 모든 job을 선택
            while (jobIndex < jobs.length && jobs[jobIndex][0] <= endTime) {
                executablePriorityQueue.add(jobs[jobIndex]);
                jobIndex ++;
            }

            // 만약 아무것도 선택된 job이 없으면 현재 endTime보다 작은 startTime을 가지는 job이 없는것
            if (executablePriorityQueue.isEmpty()) {
                endTime = jobs[jobIndex][0];
                continue;
            }

            // 수행 가능한 job 중 가장 수행시간이 짧은것을 뽑아 수행
            int[] job = executablePriorityQueue.poll();
            int arrivedTime = job[0];
            int elapseTime = job[1];
            waitTime += endTime - arrivedTime;
            waitTime += elapseTime;
            endTime += elapseTime;
            executedCnt += 1;
        }

        return waitTime / jobs.length;
    }
}