문제 요약

각 작업들의 요청 시간, 소요 시간이 주어질 때, 작업들의 요청부터 종료 시간의 최소 평균을 구하는 문제

풀이 요약

1. 두 개의 heap을 이용함
   1) 주어진 매개변수 jobs와 요청된 작업들을 저장할 heap
   2) jobs에는 요청 시간, heap에는 소요 시간을 기준으로 최소힙 구현

2. time 변수에 현재 시간을 구하고 answer 변수에는 평균을 구하기 위한 총합을 저장

3. jobs에서 현재 시간(time)보다 먼저 요청된 작업들을 heappop하여 heap변수에 저장

4. 만약 heappop 중 요청 시간이 현재 시간보다 느리다면
   1) heap이 비어있다면, time을 요청 시간으로 미룬 다음, heap에 작업 저장 (문제 조건 중, 작업이 아니라면 요청이 들어온 작업을 반드시 한다는 조건이 있음)
   2) 아니라면, 현재 heap에 있는 작업 중 소요 시간이 가장 적은 작업을 heappop하여 계산

5. 모든 jobs의 작업들이 heap에서 관리한다면, heap이 없을 때까지, 작업을 진행

코드

import heapq as hq

def solution(jobs):
    answer = 0
    n = len(jobs)
    hq.heapify(jobs)
    time = 0
    heap = list()
    
    while jobs:
        s, e = hq.heappop(jobs)
        if s > time:
            if heap:
                hq.heappush(jobs,[s,e])  
            else:
                time = s
                hq.heappush(heap,[e,s])
            
            next_t, next_s = hq.heappop(heap)
            time += next_t
            answer += time - next_s
            continue
        else:
            hq.heappush(heap,[e,s])
    
    while heap:
        e, s = hq.heappop(heap)
        time += e
        answer += time - s
        
    return answer // n