You run k identical servers, numbered 0 to k - 1, all free at time 0. Jobs arrive one at a time: jobs[i] = (arrival, duration), listed in order of arrival.
Each job, in list order, goes to the server whose free time is earliest (so an idle server that has been idle longest wins, and if every server is busy, the one that finishes soonest). Ties go to the lowest-numbered server. The job starts at max(arrival, that server's free time) and keeps the server busy for duration, so the server's new free time is start + duration.
Write assign_servers(k: int, jobs: list[tuple[int, int]]) -> list[int] that returns the server number each job runs on.
assign_servers(2, [(0, 5), (1, 2), (2, 1), (8, 3), (8, 2)])
# [0, 1, 1, 1, 0]
# job 0: both servers free since 0, tie -> server 0, busy 0..5
# job 1: server 1 (free since 0), busy 1..3
# job 2: server 1 frees at 3, before server 0 (5) -> server 1, busy 3..4
# job 3: arrives at 8; server 1 free since 4, server 0 since 5 -> server 1, busy 8..11
# job 4: server 0 (free since 5) -> server 0, busy 8..10
assign_servers(3, [(0, 1), (0, 1), (0, 1), (0, 1)])
# [0, 1, 2, 0] (the fourth job waits for server 0, which frees first at 1)
1 <= k <= 100,000, up to 100,000 jobs (possibly none),arrivalis non-decreasing down the list with0 <= arrival <= 10**9,1 <= duration <= 10**6.- Free times can pass
2**31; Python ints don't care, but use 64-bit integers in C++/Java. - Checking all
kservers for every job is O(n·k), too slow when both are large. The tests need O((n + k) log k).
This is the core move of heap scheduling: keep a min-heap of (free_time, server) pairs. The top is always the server the next job should get, and tuples compare by free time first, then by server number, which is exactly the tie rule.
Show hint
start the heap with (0, s) for every server (already a valid heap, since it's sorted). For each job, pop the top, compute start = max(arrival, free_time), record the server, and push (start + duration, server) back. heapq.heapreplace does the pop and push in one step.