Bank Tellers: Wait Time

Part (a) — how long until I'm served?

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

Part (b) — minimum time to finish M customers

Same agents, but customers are assigned optimally and agents serve back to back: the smallest T with sum over i of floor(T / times[i]) >= M.

times = [2, 3, 1, 5], M = 5  =>  3     (T=2: 1+0+2+0 = 3; T=3: 1+1+3+0 = 5)

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

Follow-ups

• Why does the heap break ties toward the lowest agent correctly?
• What is a cheap, safe upper bound for the binary search?
• M is 10^9 — can part (a) avoid simulating every customer?
• What changes when each customer needs a different amount of service?