[코딩테스트 연습] 디스크 컨트롤러

 

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

---

문제 조건 중 아래의 조건 때문에 그리디로 해결할 수 없는 문제입니다.

하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

 

디스크 컨트롤러가 처리해야 할 상황은 두 가지로 나눌 수 있습니다.

1. 현재 디스크 컨트롤러가 위치하는 시간 < 가장 우선처리 해야 할 작업의 시작시간

2. 현재 디스크 컨트롤러가 위치하는 시간 >= 가장 우선처리 해야 할 작업의 시작시간 

 

1번 케이스의 경우 작업을 수행하고 있지 않은 경우이니 그냥 가장 시작시점이 빠른 작업을 수행합니다.

2번의 경우 흔히 말하는 SJF(Shortest Job First)로 해결하면 됩니다.

즉, 현재 디스크 컨트롤러가 위치하는 시간보다 이전에 시작하는 작업들 중,

가장 먼저 처리해야 할 작업만 처리하면 됩니다.

 

위 과정을 우선순위큐 2개를 사용하여 해결했습니다.

 

첫 번째 우선순위큐는 들어온 작업이 시작순서대로 오름차순 정렬되어 있는 우선순위큐

두 번째 우선순위큐는 2번의 경우를 처리하기 위한 별도의 우선순위큐

(1st.작업시간, 2nd.작업이 끝나는 시간, 3rd.작업이 시작하는 시간순으로 오름차순 정렬) 

 

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42627.cc