디스크 컨트롤러

• 일종의 스케쥴링 문제이다. 보통 그리디로 많이 풀리기는 하는데, 조건이 조금씩 바뀔때마다 어떤 것을 먼저 선택해야 할지 기준도 달라져서, 경우에 따라서는 꽤나 어려울 때도 있다. 다행히 이 문제는 별로 어렵지 않게, 대기중인 작업중 소요시간이 가장 작은 작업부터 시작하면 된다.
• 항상 그리디는 엄밀하게 증명하려면 복잡해진다. 간략히 설명만 하면..
  • 진행중인 작업이 없을때, 이미 요청이 들어와있는 작업을 시작하지 않고 기다리는 것은 최적해가 될 수 없다. (증명 생략)
  • 진행중이던 작업X가 끝난 시점에서, A,B 작업에 대한 요청이 들어와 있었다고 하자. A와 B중 어떤 요청이 먼저 들어왔는지는 중요치 않다. 각 작업에 대해 여태까지 대기했던 시간은 이미 지나가버린거라서 바꿀수 없고, 지금 시점부터 종료시간까지의 합을 최소화 하는게 중요하다. T(A), T(B)를 A의 소요시간과 B의 소요시간이라고 하면, A를 먼저 하고 A가 끝나면 바로 B를 한다고 했을때, A가 종료까지 걸리는 시간은 T(A), B가 종료까지 걸리는 시간은 T(A)+T(B), 둘의 합은 2T(A)+T(B). 반대로 B를 먼저 하면 합은 T(A)+2T(B). T(A)<T(B)일 경우에는 A를 먼저하는 것이 더 효율적이다. 같은 원리로 대기중인 작업이 A,B 2개가 아니라 더 많은 경우에도 가장 소요시간이 적은것부터 처리하면 된다.
• 구현은 그냥 이대로 하면 된다. 대기중인 작업을 우선순위큐를 이용해서 관리하면, 소요시간이 가장 작은 작업을 O(logn)에 찾을 수 있다.
• 처음에 작업들을 요청 시간을 기준으로 정렬해야 하니까 O(nlogn)이 걸리고, 그 뒤 n개의 작업들이 한번씩 우선순위큐에 push되었다가 pop되어야 하므로 이것도 전부 O(nlogn)이 든다. 결국 총 시간복잡도도 O(nlogn)

"""Solution code for "Programmers 42627. 디스크 컨트롤러".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42627
- Solution link: http://www.teferi.net/ps/problems/programmers/42627
"""

import heapq


def solution(jobs):
    total_time = 0
    current_time = 0        
    job_count = len(jobs)
    jobs.sort(reverse=True)
    job_heap = []    
    for _ in range(job_count):
        while jobs:
            requested_time, execution_time = jobs[-1]
            if requested_time > current_time:
                break
            heapq.heappush(job_heap, (execution_time, requested_time))
            jobs.pop()
        if job_heap:
            execution_time, requested_time = heapq.heappop(job_heap)
            current_time += execution_time
        else:
            requested_time, execution_time = jobs.pop()
            current_time = requested_time + execution_time
        total_time += current_time - requested_time
    
    return total_time // job_count