선입 선출 스케줄링

• 먼저 n번째 작업이 시작되는 시간을 파라메트릭 서치를 통해서 구하고, 그것으로부터 몇 번 작업인지를 구한다.
• f(t)를 t시간까지 시작된 작업의 갯수라고 하면, 이것을 구하는 것은 간단하다.
  • 각각의 코어가 몇개의 작업을 했는지 구해서 다 합하면 된다. 시간복잡도는 O(m), (m = core의 수)
• f(t)>=n 을 만족하는 최소의 t는 [0, k*n] 범위 안에서 이분검색으로 구할 수 있다 (k는 코어당 작업을 처리하는 최대 시간, 문제에서는 k=10000). O(logkn)번의 탐색으로 구해진다
  • 탐색 범위는 여러 방법으로 더 좁힐 수 있다. 예를 들면, 상한을 min(cores)*n 으로 쓸 수 있다. 이것은 가장 빠른 코어 한개로 작업 n개를 처리하는 시간인데, 실제 시간은 여러개의 코어를 돌리니 당연히 이것보다 짧을 것이므로 가능하다. 아니면, m개의 코어로 작업하되 모든 코어가 max(cores)일 경우에 걸리는 시간인 max(cores)* ceil(n/len(cores)) 를 상한으로 잡는 것도 가능하다. 이렇게 쓰면 횟수를 O(log(nk/m))으로 복잡도를 쓸 수 있어서 좀 더 멋있다.
• 총 탐색시간은 두개를 곱해서 O(mlog(nk/m))
• 이렇게 n번째 작업이 시작되는 시간 t를 구하면, 작업 번호를 구하면 된다. t-1 시간까지 끝난 작업 갯수를 구해서, 그개 n-i이라면, t시간에 시작되는 작업들 중에서 i번째의 작업 번호를 출력하면 된다. 이것도 O(m)에 끝난다.
• 전체 프로세스의 복잡도는 O(mlog(nk/m))
• 만약, 그냥 힙을 이용해서 작업이 시작되고 끝나는 것을 시뮬레이션 하는 식으로 처리하면 O(nlogm)이 걸린다. n과 m이 5배밖에 차이가 안나서, 파라메트릭 서치로 푼 정답과 실제 수행시간이 크게 차이나지는 않을 것 같은데, 이렇게 풀면 타임오버가 나도록 절묘하게 시간 세팅을 잘 해놓았다..

"""Solution code for "Programmers 12920. 선입 선출 스케줄링".

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

from teflib import algorithm


def solution(n, cores):

    def predicate(t):
        work_count = sum((t // core) + 1 for core in cores)
        return work_count >= n

    t = algorithm.binary_search(0, min(cores) * n, predicate)
    starting_cores_at_t = [i for i, core in enumerate(cores) if t % core == 0]
    started_before_t = sum(((t - 1) // core) + 1 for core in cores)
    return starting_cores_at_t[n - started_before_t - 1] + 1

• Dependency: teflib.algorithm.binary_search