Algorithms & Data Structuresmedium

Bank Tellers I

A bank has N agents; agent i always takes times[i] minutes per customer. Customers wait in one queue and there are M customers ahead of you. All agents are free at time 0; whenever one frees up, the next customer walks over. If several free up at the same moment, the lowest-numbered agent takes the next customer. Return the time at which an agent starts serving you.

times = [2, 3, 1, 5], M = 5  =>  2
t=0: customers 1-4 take agents 0,1,2,3 (free again at 2,3,1,5)
t=1: agent 2 frees -> customer 5 (free again at 2)
t=2: agents 0 and 2 both free -> you go to agent 0

N up to 10^5, times[i] up to 10^7.

Hints

Hint 1

A min-heap of (freeTime, agentIndex). Tuple ordering gives the tie-break for free — equal times pop the lower index first.

Hint 2

Serve the M customers ahead of you by popping and pushing (freeTime + times[agent], agent); your start time is the freeTime of the next pop.

Hints

Asked at