Problem overview
Worker i in a factory needs times[i] units of time to pack one product. The function min_time takes times and k and returns the smallest amount of time in which all the workers together pack at least k products.
For times = [4, 7, 3, 6, 7, 1] and k = 60 the answer is 30. In 30 units the workers pack 7, 4, 10, 5, 4 and 30 products, which is 60. In 29 units they pack 7 + 4 + 9 + 4 + 4 + 29 = 57, which is not enough.
This version must run in O(n * log(k * T)) time, where T is the largest time of a single worker, with O(1) extra space.
Approach: binary search on the answer
The first lesson on this problem tried every time 0, 1, 2, … and stopped at the first that packed enough, which is slow when the answer is large. The key fact that makes it faster: the number of products is non-decreasing in time. So the times split into two blocks: first the times that are too short (fewer than k products), then the times that are enough (at least k). The answer is where the second block starts, and binary search can find such a boundary without looking at every time.
The search needs a range to start from:
- The lowest sensible time is 1. (Time 0 packs nothing, and
kis positive.) - The fastest worker alone packs
kproducts inmin_value * kunits, so the answer is at most that. The whole team can only be faster.
Each step tests the middle time with the same counting helper as before: how many products do the workers pack in mid units? If that is below k, the answer is above mid. Otherwise mid works, so remember it and look for something shorter.
For the example, the range is 1 to 60. The middle, 30, packs exactly 60, so it is remembered and the range becomes 1 to 29. Then 15 packs 29, which is too few, so the range is 16 to 29. Then 22 packs 43 (too few), 26 packs 50 (too few) and 28 packs 56 (too few), and finally 29 packs 57 (too few). The range empties, and the remembered 30 is the answer.
Step by step
- Find the fastest worker.
*times.iter().min().unwrap():minreturns anOption<&i32>,unwraptakes the reference out, and*copies the number. - Set the bounds.
leftstarts at1i32andrightatmin_value.saturating_mul(k), which stops ati32::MAXinstead of overflowing. - Keep the best time so far in a mutable
time, starting at0i32. - Loop while
left <= right, so the range still holds a candidate. - Take the middle as
mid = left + (right - left) / 2. - If
midpacks fewer thankproducts, it is too short:left = mid + 1. - Otherwise
midis enough. Record it withtime = mid;and look for a shorter time withright = mid - 1;. - Return
time, the smallest time found that packskproducts. - Write the helper
count_products(times: &[i32], time: i32) -> i32, which borrows the times as a slice. - Make its body one iterator chain:
times.iter().map(|&t| time / t).sum(). Each worker packstime / tproducts (integer division), andsumadds them up.
The solution in Rust
impl Solution {
fn count_products(times: &[i32], time: i32) -> i32 {
times.iter().map(|&t| time / t).sum()
}
fn min_time(times: Vec<i32>, k: i32) -> i32 {
let min_value = *times.iter().min().unwrap();
let mut left = 1i32;
let mut right = min_value.saturating_mul(k);
let mut time = 0i32;
while left <= right {
let mid = left + (right - left) / 2;
if Self::count_products(×, mid) < k {
left = mid + 1;
} else {
time = mid;
right = mid - 1;
}
}
time
}
}
Rust details worth a look:
Optionandunwrap.min()returnsNonefor an empty vector, andunwrap()onNonepanics. The problem always has at least one worker.saturating_mul. A plain*on twoi32values wraps around silently in an optimized build, which is how the lessons are built, and panics in a debug build.saturating_mulclamps the result to the range ofi32instead. For example,2_000_000_000i32.saturating_mul(2)is2147483647.- The overflow-safe midpoint.
left + (right - left) / 2never exceedsright, while(left + right) / 2can overflow when both are large. - Why
timeis recorded inside theelse. The last middle the loop examines can be one that was too short, so the finalmidis not necessarily the answer. The recorded value is. - Slices and the tail expression.
×lends the vector to the helper as a&[i32]without moving it, and the lines with no semicolon are the return values.
Complexity
Time: O(n * log(k * T)). The search range has at most k * T values, so the loop runs about log₂(k * T) times. Each iteration calls count_products, which costs O(n). Finding the minimum adds one more O(n) pass.
Space: O(1). Only a few integers are stored, and the helper borrows the vector.
Edge cases and common mistakes
- One worker.
times = [5]withk = 1gives 5, andtimes = [3, 3]withk = 4gives 6. k = 0. The range is 1 to 0, so the loop never runs and the function returns 0.- Answers beyond the
i32range. If the true answer doesn't fit in ani32, for instance with two workers of 1,000,000,000 units each andk = 1000000,left + 1eventually overflows and the loop never ends in an optimized build. Inputs of that size are outside what the lesson's tests use. - Forgetting to record
time. Returningmidorleftinstead gives wrong answers when the last probe was too short. - Moving the wrong bound. A time that packs enough must shrink
right(to look for something smaller), and a time that packs too few must growleft. - Starting
leftat 0. It is harmless but wastes a step, as time 0 can't be an answer for a positivek.
Testing
times = [4, 7, 3, 6, 7, 1],k = 60gives30.times = [5],k = 1gives5.times = [2, 3],k = 7gives9.times = [3, 3],k = 4gives6.
