def solution(n, cores):
min_ = min(cores) * (n//len(cores))
max_ = max(cores)* (n//len(cores))
while min_ < max_ :
t = (min_+max_)//2
cnt_jobs = sum(t//core + 1 for core in cores)
if cnt_jobs >= n :
max_ = t
else :
min_ = t + 1
free_cores_at_t = [i for i, core in enumerate(cores) if min_ % core == 0]
left_jobs_at_t = n - sum((min_-1)//core + 1 for core in cores)
return free_cores_at_t[left_jobs_at_t - 1] + 1
알고리즘
n번째 작업이 시작되는 시간t를 구한다.
t시간에 놀고있는 코어들을 구한다.
t시간에 시작해야할 작업들의 개수를 구한다.
n-t-1시간에 끝난 작업 개수
t시간에 놀고있는 코어 중t시간에 시작해야할 적업의 개수-1 번째 코어가 마지막 작업을 수행하는 코어다.
코어의 상태
처리시간이 c 인 코어는 t시에
t/c개의 작업을 이미 처리했고1개의 작업이 시작됨
라고 이해하면된다.
n번째 작업이 시작되는 시간 t 는 이진탐색으로 쉽게 찾아 줄 수 있다. 그리고 t 시간에 새로운 작업이 시작되는 코어들은 t시간이 딱 되자마자 작업을 끝내고 놀고있는 코어로 볼 수 있다(하나의 작업이 끝나자마자 시작되는 문제 설정 때문에 논리적 시각으로 작업이 끝나고 놀다가 시작된다라고 볼 수 있음).
free_cores_at_t = [i for i, core in enumerate(cores) if min_ % core == 0]
t 시에 남은 작업의 개수
# n - ('t-1 시간에 끝낸작업 개수' + `t-1` 시간에 시작된 작업 개수)
left_jobs_at_t = n - sum((min_-1)//core + 1 for core in cores)
t 시간에 놀고있는 코어와, t 시간에 남은 작업의 개수를 알면된다.
def solution(n, cores):
min_ = min(cores) * (n//len(cores))
max_ = max(cores)* (n//len(cores))
while min_ < max_ :
t = (min_+max_)//2
cnt_jobs = sum(t//core + 1 for core in cores)
if cnt_jobs >= n :
max_ = t
else :
min_ = t + 1
free_cores_at_t = [i for i, core in enumerate(cores) if min_ % core == 0]
left_jobs_at_t = n - sum((min_-1)//core + 1 for core in cores)
return free_cores_at_t[left_jobs_at_t - 1] + 1