https://programmers.co.kr/learn/courses/30/lessons/42627
-
flow
특정 시점일때, 요청이 들어와서 처리가 가능한 작업중 가장 짧은 작업을 선택해 나아가면 된다. 예시같은경우 처음 시점 0ms 일때, A만 가능하므로 A선택, A는 3ms 걸리므로 다음 시점은 3ms, 이 때 가능한 작업들은 요청 들어온 시간이 1ms, 2ms, 3ms 인 작업들.. B와 C해당.. 이 중에서 선택할 때, 요청 들어온 시간은 아무 소용없고, 단순히 작업시간이 짧은 것 선택 -> C 선택.. C는 6ms 걸리므로 다음시점 9ms 일때 wait 작업들 예시에서는 B만 남았지만 다른 작업이 더 있었다면 B를 포함해서 wait 하고 있는 애들 계속 비교하면 됨.
중간에 wait하고 있는 작업이 없는 경우가 있음. 그럴땐 시점을 단위인 1ms 이후일 때 확인, 계속 없으면 늘려나가면 됨.
처음에 주어진 input Jobs 에서 remove 나 pop 으로 빼내려 했는데 반복문 중간에 remove나 pop 쓰는 순간 귀찮아져서(단순히 index 찾아놓고 반복문 끝난 이후 적용 가능하긴 하지만 귀찮았음..) 계속 시점마다 wait 작업을 추가로 찾을 때, 모든 job 을 탐색하게끔 코드가 짜여져 있음.. 그리고 카테고리가 힙이라 최소힙을 사용하여 wait list 중 그때 그때 최소값을 찾아내면 됨. 이것만 주의하면 시간 복잡도는 O(NlogN).. 최악인 경우가 길이가 N인 힙을 생성하는 경우이기 때문 -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A5.py
