두 방법 중 SJF가 무조건 빠르므로 SJF만 구현
def solution(jobs):
total, num = 0, len(jobs)
jobs.sort()
start, time = jobs.pop(0)
total += time
clock = start + time
while jobs:
idx = 0
for i in range(1, len(jobs)):
if jobs[i][0]<=clock and jobs[i][1]<jobs[idx][1]: idx = i
start, time = jobs.pop(idx)
if start <= clock:
total += (clock-start) + time
clock += time
else:
total += time
clock = start + time
return total//num정렬하고 첫번째 작업은 무조건 실행
작업이 끝난 시간보다 먼저 들어와있는 작업 중 가장 짧게 걸리는 작업을 먼저 실행
작업이 끝나는 시간과 요청이 들어오는 시간의 간격이 있는 작업은 첫번째 작업과 같은 방식으로 시간 계산
heapq를 활용한 코드
import heapq
def solution(jobs):
total, clock, start, n = 0, 0, -1, len(jobs)
heap = []
while n>0:
for s, t in jobs:
if start<s<=clock: heapq.heappush(heap, [t, s])
if heap:
job = heapq.heappop(heap)
start = clock
clock += job[0]
total += clock - job[1]
n -= 1
else: clock += 1
return total//len(jobs)clock에 맞춰 요청이 들어온 순서대로 heapq에 push
heapq에서 실행 시간이 짧은 순서로 정렬될 수 있게 배열 변경
clock은 작업이 실행될 때는 실행 시간만큼 더해지고 실행되지 않는 경우에는 +1
