Find the Smallest Batch Size That Keeps Total Processing Rounds Within a Limit
Solve this Problemsizes 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.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of jobs ≤ 5 × 10⁴ - ◆
1 ≤ sizes[i] ≤ 10⁶ - ◆
number of jobs ≤ threshold ≤ 10⁶
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Batch Size From 1 Upward
BruteA job of size s processed in batches of d items needs ⌈s / d⌉ rounds — any leftover items still need one more round. Try d = 1, 2, 3, ... and for each one add up every job's rounds; the first batch size whose total fits within threshold is the answer, since a bigger batch size can only ever need the same number of rounds or fewer. Correct, but checking every candidate size one at a time is wasteful once job sizes get large.
O(n · maxSize)O(1)1class Solution {
2 public int smallestBatchSize(int[] sizes, int threshold) {
3 int maxSize = 0;
4 for (int s : sizes) maxSize = Math.max(maxSize, s);
5 for (int d = 1; d <= maxSize; d++) {
6 long total = 0;
7 for (int s : sizes) total += (s + d - 1) / d;
8 if (total <= threshold) return d;
9 }
10 return maxSize;
11 }
12}Optimal — Binary Search on the Batch Size
OptimalThe total rounds needed only ever goes down (or stays the same) as the batch size grows — a bigger batch can never need more rounds per job. That monotonic relationship is exactly what binary search needs: search the candidate batch sizes from 1 to the largest job, and whenever a candidate's total rounds fits within threshold, remember it and try a smaller batch size; otherwise the batch is too small, so search bigger.
O(n · log(maxSize))O(1)1class Solution {
2 public int smallestBatchSize(int[] sizes, int threshold) {
3 int lo = 1, hi = 0;
4 for (int s : sizes) hi = Math.max(hi, s);
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 long total = 0;
9 for (int s : sizes) total += (s + mid - 1) / mid;
10 if (total <= threshold) {
11 ans = mid;
12 hi = mid - 1;
13 } else {
14 lo = mid + 1;
15 }
16 }
17 return ans;
18 }
19}