[디스크 컨트롤러/LV3/Python3]

디스크 컨트롤러 LV3

 

문제 설명
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.


제한 사항
1 ≤ jobs의 길이 ≤ 500
jobs [i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다. s는 작업이 요청되는 시점이며 0 ≤ s ≤ 1,000입니다. l은 작업의 소요시간이며 1 ≤ l ≤ 1,000입니다.


입출력 예

jobs	return
[[0, 3], [1, 9], [3, 5]	8

 

 

우선순위 큐로 문제를 해결했다.

우선순위 큐에 넣으면 최소힙이 우선으로 나오기 때문에, 기본적으로 문제에 맞는 우선순위가 맞춰진다.

끝나는 시간을 지속적으로 증가하면서, 각 작업이 끝날 때의 시간을 측정하였다.

 

마지막에 모든 작업에 대해 시작 시간을 빼어 선반영 된 시간을 해결했다.

 

 

import heapq

def solution(jobs):
    jobs.sort()
    heap = []

    endTime = jobs[0][1] + jobs[0][0]
    answer = jobs[0][1] + jobs[0][0]

    for i in range(1, len(jobs)):
        while len(heap) > 0 and endTime <= jobs[i][0]:
            endTime += heapq.heappop(heap)
            answer += endTime

        if jobs[i][0] > endTime:
            endTime += jobs[i][0] - endTime
        heapq.heappush(heap, jobs[i][1])


    while len(heap) > 0:
        endTime += heapq.heappop(heap)
        answer += endTime
        
    
    for i in range(len(jobs)):
        answer -= jobs[i][0]
        
    return answer // len(jobs)