문제

풀이

조건에 따르면 작업을 수행하고 있지 않을 때는 먼저 요청이 들어온 작업부터 처리해야 한다. 작업을 처리하는 동안 요청이 들어오면 따로 저장해 두었다가, 처리 시간이 짧은 작업부터 처리하면 된다. 전체 처리 시간을 줄여야 하는데 대기 중인 작업이 있는 동안 처리하는 작업에 소요된 시간은 대기 중인 모든 작업의 처리 시간을 늘리기 때문이다. 소요시간 순으로 정렬하기 위해 힙을 이용하였다. 힙에 있는 대기 작업을 하나씩 꺼내서 실행하는 동안에도 새로운 요청이 들어올 경우 즉시 힙에 넣어줘야 한다는 사실에 주의해야 한다. 입력으로 주어지는 jobs 배열이 요청 시간 순으로 배열되도록 한 번 정렬해 줘야 한다.

코드

import heapq

def solution(jobs):
    N = len(jobs)
    answer = 0
    current = 0
    jobs.sort()
    q = []
    
    while jobs:
        while jobs and jobs[0][0] < current:
            heapq.heappush(q, jobs.pop(0)[::-1])
        if q:
            duration, start = heapq.heappop(q)
            current += duration
            answer += current - start
        else:
            start, duration = jobs.pop(0)
            current = start + duration
            answer += duration
                
    while q:
        duration, start = heapq.heappop(q)
        current += duration
        answer += current - start
        
    return answer // N

사족

구현 아이디어는 간단한 편인데 반복 조건을 설정하는 게 헷갈려서 여러 번 코드를 새로 짰다. 최종 완성된 코드가 반복문의 중첩이 제일 적고 깔끔한 것 같아 만족스럽다.