Lowest consumer rate that drains a queue in time
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A consumer works through message batches one at a time, in order. At a rate of r messages per second, a batch of m messages takes ceil(m / r) whole seconds; a second left over at the end of a batch is not used for the next one.
Return the lowest whole rate r that finishes every batch within seconds seconds. There is always one: seconds is at least the number of batches.
- 1 ≤ batches.length ≤ 200,000
- 1 ≤ batches[i] ≤ 10⁹
- batches.length ≤ seconds ≤ 10⁹
Examples
lowestRate([3, 6, 7, 11], 8)returns4At 4 a second the batches take 1, 2, 2 and 3 seconds: 8 in all. At 3 they take 1, 2, 3 and 4: 10.lowestRate([30, 11, 23, 4, 20], 5)returns30One second per batch, so the rate must cover the largest batch.lowestRate([1], 1000)returns1
Hints
Hint 1 of 2
If a rate works, every higher rate works too. So "does rate r finish in time?" flips once, from no to yes, as r grows.
Hint 2 of 2
Search r between 1 and the largest batch: at the largest batch every batch takes one second, which always fits.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Nothing here is sorted, but the question is. A faster consumer never takes longer, so "rate r finishes in time" is false for every rate below some threshold and true for every rate from it on. That threshold is the answer, and a boundary like that is what binary search finds.
Checking one rate is a single pass: add up Math.ceil(m / r) and stop early once the total passes seconds. The range of rates runs from 1 to the largest batch, because at that rate every batch takes exactly one second and there are at most seconds batches.
One trap at this size: Math.max(...batches) passes 200,000 arguments to one call, which overflows the call stack in most engines. Find the largest batch with a loop or reduce.
Rounding matters. Math.floor pretends the spare part of a second carries over to the next batch, which makes slow rates look fast enough. Trying rates one by one gives the right answer but can need a billion checks.
function lowestRate(batches, seconds) {
const fits = (r) => {
let total = 0;
for (const m of batches) {
total += Math.ceil(m / r);
if (total > seconds) return false;
}
return true;
};
let lo = 1, hi = batches.reduce((a, b) => Math.max(a, b), 0);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (fits(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}Complexity. O(n log M) for n batches and a largest batch of M: about thirty passes over the batches.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.