[Programmers] 디스크 컨트롤러

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

---

먼저 시작시간이 가장 빠르고, 시작시간이 같다면 소요시간이 적은 순으로 jobs를 정렬한다.

마지막 작업이 종료된 시간(let, 종료시간)을 저장하는 변수를 하나 만들고 0으로 초기화시킨다.

가장 먼저 시작되는건 jobs의 첫번째 요소일 것이다.

 

작업 소요시간이 적은 순으로 정렬되는 최소힙을 하나만들어서 가장 먼저 시작되는 jobs의첫번째 요소를 큐에 넣는다.

이제 최소힙 빌때까지 잡들의 최소 소요시간을 구해서 sum 변수에 더해나간다.

 

최소힙의 첫번째 요소를 꺼내서 job의 실제 시작시간을 구한다.

만일 이전 잡의 종료시간이 현재 job의 시작시간보다 작거나 같으면 현재 job의 시작시간이 실제 시작시간이 될 것이고,

이전 잡의 종료시간이 현재 job의 시작시간보다 크면 이전잡의 종료시간이 실제 시작시간이 될 것이다.

현재 job의 실제 종료시간은 실제시작시간 + job의 소요시간이 될 것이다.

현재 job의 실제 소요시간은

실제종료시간 - 현재 job의 시작시간

= (실제시작시간 + 현재 job의 소요시간) - 현재 job의 시작시간

= (max(이전job의 종료시간, 현재job의시작시간) + 현재 job의 소요시간 ) - 현재 job의 시작시간

이다.

 

sum을 갱신했으면 이제 최소힙을 갱신한다.

최소힙엔 다음에 시작될수 있는 job들을 추가한다.

종료시간보다 시작시간이 작거나 같은 job들(i) 은 다음에 시작될 수 있는 job들이기 때문에 추가한다.

만일 아직 실행되어야 하는 job들이 남았음에도 모든 잔여 job들의 시작시간이 현재까지의 job들의 종료시간보다 크다면  (i) 조건으로는 큐에 추가되지 않는다. 따라서 (i) 조건을 충족시키지 않더라도 남은 job이 있고 큐가 비어있다면 남은 job들 중 시작시간이 가장 작은 job을 큐에 추가한다.

 

위 과정들을 모든 job을 탐색할때까지 반복한다.

 

시간복잡도는 O(NlogN). N = |jobs|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Heap/%EB%94%94%EC%8A%A4%ED%81%AC%20%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC.cpp