[Level 3] 디스크 컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/42627#

코딩테스트 연습 - 디스크 컨트롤러

---

접근

힙을 활용했다. job의 시작시간이 특정 시간의 범위 내에 있을 때 힙에 넣는다. 힙에 넣을 때는 작업이 소요되는 시간을 기준으로 넣을 수 있도록 한다. 여기서 힙이 비어있을 때는 시간을 1씩 증가하도록 한다.

 

구현

- 먼저 지난 시간 last를 -1, 현재 시간 cur을 jobs 중에 가장 빠른 시작시간으로 초기화한다.

- 이제 while문을 통해 작업의 개수인 count가 jobs의 길이만큼 했을 때 종료하도록 한다.

- 먼저 jobs를 탐색하여 지난 시간과 현재시간 사이에 시작하는 job을 힙에 넣도록 한다.

- 이를 통해 작업을 할 수 있는 시간을 찾고 이 중에서 소요 시간이 가장 적은 것을 먼저 할 수 있도록 한다.

- 이제 소요시간이 가장 적은 작업을 꺼내서 현재 시간 - 작업의 시작 시간을 answer에 더한다.

- 하지만 heap에 원소가 없을 때는 현재 시간을 1씩 증가한다.

from heapq import heapify, heappush, heappop
def solution(jobs):
    answer = 0
    jobs.sort()
    last, cur = -1, jobs[0][0]
    heap = []
    count = 0
    while count < len(jobs):
        for s, t in jobs:
            if last < s <= cur:
                heappush(heap, [t, s])
        if heap:
            last = cur
            term, start = heappop(heap)
            cur += term
            answer += (cur - start)
            count += 1
        else:
            cur += 1
    answer //= len(jobs)
    return answer