최소작업 우선 스케줄링이란 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당하는 방법이다.
Pros
Cons
import heapq
def solution(jobs:list) -> int:
"""[summary]
Programmers 디스크 컨트롤러 문제
SJF(Shortest Job First) Scheduling Algorithm
- it has the shortest mean waiting time
- it choose a shorter processing time
Args:
jobs (list): [Arrival_time, Processing_time]
Returns:
int: 작업의 요청부터 종료까지 걸린 time의 평균
"""
ans = 0
jobs.sort()
# 1. init settings
works = []
N = len(jobs)
# 2. SJF Scheduling
## element: [Processing_time, Arrival_time]
cur_time = 0
while jobs or works:
if not works:
a_t, p_t = jobs.pop(0)
heapq.heappush(works, [p_t, a_t])
continue
w_p_t, w_a_t = heapq.heappop(works)
if cur_time > w_a_t:
ans += w_p_t + (cur_time - w_a_t)
cur_time += w_p_t
else:
ans += w_p_t
cur_time = w_p_t + w_a_t
while jobs:
a_t, p_t = jobs[0]
if a_t < cur_time:
heapq.heappush(works, [p_t, a_t])
jobs.pop(0)
else:
break
ans //= N
return ans
print(solution([[0,3], [1,9], [2,6]]))
print(solution([[1, 9], [1, 7], [0, 3]]))