선입 선출 스케줄링

https://school.programmers.co.kr/learn/courses/30/lessons/12920

Explanation

Firstly, before we do anything, if n is less than length than length of cores, than we can just return n. But the problem is finding when n is bigger and we have to find the index. I think it is binary search but how do I know what to guess? Surely I cannot guess the index?

In this example, what we need to guess is the hard part - we can guess the time for all n processes to be done. But how do we get the index then? We get the time not when all n processes are done, but just 1 time frame back before. Then, for the last iteration, we iterate core by core for the remaining n jobs and find the index.

So in this example, which I took very long to understand, we can find the perfect minimum time that all cores can run and complete n tasks. But the question is not asking for the minimum time. We want to find the index of core that completes the last job. So we need to take a step back and go back 1 time frame back from that minimum time and see how many jobs are completed up to 1 time frame before that minimum time. That is why we use start-1 to get the previous time and minus all the jobs that cores completed within that time. That will result in x remaining jobs to be completed left for the final iteration. We iterate manually through the index of cores for time frame = start (minimum time).

When start%cores[i]==0, we decrement n by 1 and once n reaches 0, that is when that index of core will be the one that takes this job so return that index+1 (+1 cuz not 0-indexed).

correct solution


def solution(n, cores):
    if n <= len(cores):
        return n
    
    n -= len(cores)
    start = 1
    end = max(cores) * n
    while start<= end:
        mid = (start+end)//2
        jobs_completed = sum(mid//core for core in cores)
        if jobs_completed >=n:
            end=mid-1
        else:
            start = mid+1
        
    for core in cores:
        n-= (start-1)//core
    for i in range(len(cores)):
        if start%cores[i]==0:
            n-=1
            if n==0:
                return i+1