Lowest consumer rate that drains a queue in time

MediumAbout 30 minProblem 2 of 3 in Binary searchDraft

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

  1. lowestRate([3, 6, 7, 11], 8)returns 4At 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.
  2. lowestRate([30, 11, 23, 4, 20], 5)returns 30One second per batch, so the rate must cover the largest batch.
  3. lowestRate([1], 1000)returns 1

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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open