출처 https://programmers.co.kr/learn/courses/30/lessons/42627?language=python3

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다.
2차원 배열 jobs : 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간] solution 함수 : 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return (단, 소수점 이하의 수는 버립니다)

• 0ms 시점에 3ms가 소요되는 A작업 요청
• 1ms 시점에 9ms가 소요되는 B작업 요청
• 2ms 시점에 6ms가 소요되는 C작업 요청
  

요청이 들어온 순서대로 처리

각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)

각 작업의 요청부터 종료까지 걸린 시간의 평균이 최소가 되도록 처리

각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)

나의 풀이

import heapq

def solution(jobs):  
    answer, time, cnt, lenJob = 0, 0, 0, len(jobs)
    heap = [] 
    jobs.sort() 

    while cnt < lenJob: 
        while len(jobs) > 0:
            if jobs[0][0] <= time:
                heapq.heappush(heap, jobs.pop(0)[::-1])
            else:
                break
        
        if len(heap) > 0:
            job = heapq.heappop(heap) 
            time += job[0] 
            answer += time - job[1]
            cnt += 1
        else:
            time += 1

    return answer//lenJob

변수
평균 대기 시간, 현재 시간, 완료된 작업 갯수, 총 작업 갯수, 대기 힙(min heap)
answer = 0
time = 0
cnt = 0
lenJob = len(jobs)
heap = []
jobs.sort() # 정렬되어 있다는 조건이 없으므로 요청시간 기준 정렬

while문

while cnt < lenJob: 

cnt가 고정된 lenJob보다 작은 동안 while문을 돌면서 작업을 완료 할 때 마다 cnt+=1 해준다.

• 대기 힙 관리

        while len(jobs) > 0:
            if jobs[0][0] <= time:
                heapq.heappush(heap, jobs.pop(0)[::-1]) 
            else:
                break

정렬된 작업 배열 jobs에서 요청 시간이 현재 시간보다 작거나 같은 작업을 jobs에서 pop 해준 뒤 대기 힙에 넣어준다.
이 때 jobs 의 원소는 [요청시간, 작업시간] 순서로 되어있는데 대기 힙은 작업시간 기준의 min heap 이므로 jobs.pop(0)[::-1] 를 해줘 [작업시간, 요청시간] 순서로 대기 힙에 넣어준다.

• 작업 관리

        if len(heap) > 0:
            job = heapq.heappop(heap) 
            time += job[0] 
            answer += time - job[1]
            cnt += 1
        else:
            time += 1

작업 관리는 1) 대기 힙에 작업이 있는 경우, 2) 대기 힙에 작업이 없는 경우 두 가지로 나눌 수 있다.
1) 여기서 time += 1씩 해주고 작업의 남은 실행시간 변수를 관리하며 코드를 작성할까 고민했지만 어차피 작업이 실행중이라면 다른 작업은 실행 할 수 없기 불필요한 while문을 돌게 되므로 효율적이지 않다는 생각이 들었다.
그래서 그냥 바로 time을 작업 완료 시간으로 update 해주기로 했다.
time += job[0] 을 해줘 현재 시간을 해당 작업이 완료되는 시간으로 update 해준 뒤 answer += time - job[1] 해당 작업의 대기 시간을 answer에 더해줬다. cnt += 1 를 통해 완료된 작업 갯수도 update 해주었다.
2) time += 1 해주고 빠져나가 while문을 돌며 대기 힙에 작업이 들어오기를 기다려야한다.

함수 return

return answer//lenJob

다른 사람의 풀이

import heapq

def solution(jobs): 
    answer, time, cnt = 0, 0, 0
    start = -1 
    heap = []
    jobs.sort()
    
    while cnt < len(jobs):
        for j in jobs:
            if start < j[0] <= time:
                heapq.heappush(heap, [j[1], j[0]]) 
        
        if len(heap) > 0: 
            cur = heapq.heappop(heap)
            start = time
            time += cur[0]
            answer += time - cur[1] 
            cnt += 1
        else: 
            time += 1 
                
    return answer // len(jobs)

나와 풀이가 거의 비슷했지만 jobs는 유지하고 start 변수를 관리하며 while문 안에서 for문을 돌며 대기 힙에 작업을 넣어준다는 점이 달랐다.
그래서 나의 풀이와 효율성을 비교해 보았고 while 문 안에서 jobs를 pop해주는 나의 코드가 불필요한 반복을 줄여 시간 측면에서 더 효율적이라는 것을 알 수 있었다.