Find the Smallest Batch Size That Keeps Total Processing Rounds Within a Limit
Implement smallestBatchSize
Given an array
sizes where each value is the size of one job, and an integer threshold, find the smallest positive batch size that keeps the total number of processing rounds at or under threshold.
A job of size s, processed in batches of d items at a time, takes ⌈s / d⌉ rounds — even one leftover item still needs a whole extra round. Return the smallest integer batch size d for which the sum of every job's rounds fits within threshold — a solution always exists, since a batch size as large as the biggest single job needs at most one round per job.
The total number of rounds only ever decreases (or stays flat) as the batch size grows, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate batch size). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger candidate keeps working too. — search directly over candidate batch sizes rather than the jobs themselves.
Example 1:
Input: sizes = [8,14,23,3], threshold = 6
Output: 12
Example 2:
Input: sizes = [2,3,5,7,11], threshold = 11
Output: 3
Example 3:
Input: sizes = [10], threshold = 1
Output: 10
+ 5 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ number of jobs ≤ 5 × 10⁴ - ●
1 ≤ sizes[i] ≤ 10⁶ - ●
number of jobs ≤ threshold ≤ 10⁶
sizes =
[8, 14, 23, 3]
threshold =
6