Algorithms & Data Structuresmedium

Bank Tellers II

A bank has N agents; agent i takes times[i] minutes per customer and serves customers back to back. M customers are waiting, and you may assign them to agents however you like. Return the minimum time by which all M customers have been served — the smallest T such that the sum over agents of floor(T / times[i]) is at least M.

times = [2, 3, 1, 5], M = 5  =>  3
T = 2: 1 + 0 + 2 + 0 = 3 customers done
T = 3: 1 + 1 + 3 + 0 = 5 customers done

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

Hints

Hint 1

In time T, agent i finishes floor(T / times[i]) customers. That total never decreases as T grows.

Hint 2

So binary search T: lo = 1 and hi = min(times) × M, since the fastest agent alone finishes everyone by then.

Hints

Asked at