C# 디스크 컨트롤러 - 힙 / 프로그래머스 [Lv.3]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/42627

 

 

나의 풀이

public int solution(int[,] jobs) 
{
    var jobQueue = new Queue<(int requestTime, int duration)>(
        Enumerable.Range(0, jobs.GetLength(0))
            .Select(e => (jobs[e, 0], jobs[e, 1]))
            .OrderBy(e => e.Item1)
    );

    int time = 0;
    int curRequestTime = 0;
    int curRemain = 0;
    int completeTimeSum = 0;

    var jobCanStart = new List<(int requestTime, int duration)>();
    while(jobQueue.Count > 0 || jobCanStart.Count > 0 || curRemain > 0)
    {
        if(curRemain > 0)
        {
            --curRemain;
            ++time;

            if(curRemain == 0) // 완료함
                completeTimeSum += time - curRequestTime;    

            continue;
        }

        while(jobQueue.Count > 0 && jobQueue.Peek().Item1 <= time)
            jobCanStart.Add(jobQueue.Dequeue());

        if(jobCanStart.Count == 0) // 실행할 수 있는 작업이 없음
        {
            ++time;
            continue;
        }

        (int requestTime, int duration) cur = jobCanStart.OrderBy(e => e.Item2).First();
        jobCanStart.Remove(cur);

        curRequestTime = cur.requestTime;
        curRemain = cur.duration;
    }

    return completeTimeSum / jobs.GetLength(0);
}

중간에 작업을 취소할 수 없으며 하나만 실행가능하기 때문에

작업이 완료 될 때마다 현재 실행 가능한 작업 중 가장 빨리 끝낼 수 있는 것을 실행하기만 하면 된다.

 

이는 운영체제에서 최단 작업 우선(Shortest Job First, SJF) 알고리즘이라고 부른다.