runtimequestion 348 Algorithms & Complexity · medium
A round-robin job runner
A build server shares one worker fairly: each job in the queue gets a turn of at most slice_units units of work; a job that isn't finished goes to the back of the queue. Time starts at 0 and advances by the units actually worked. Write round_robin(jobs, slice_units) that returns when each job finished.
Function
round_robin(jobs, slice_units)jobsa list of
[name, units] pairs in queue order; units ≥ 1Returnsa list of
(name, finished_at) tuples in the order the jobs finishRulesa turn works
min(slice_units, remaining) units; don't change the jobs list or its pairsExamples
callround_robin([['backup', 5], ['email', 2], ['report', 3]], 2)returns[('email', 4), ('report', 9), ('backup', 10)]
callround_robin([['lint', 1], ['test', 4]], 3)returns[('lint', 1), ('test', 5)]
callround_robin([], 2)returns[]