Problem overview
A factory has workers, and worker i needs times[i] units of time to pack one product. The function min_time receives the vector times and a number k, and returns the smallest amount of time in which all the workers together can pack at least k products. Everyone works at the same time, and a worker only counts products they have finished.
In the example, times = [4, 7, 3, 6, 7, 1] and k = 60. After 30 units of time the workers have packed 7, 4, 10, 5, 4 and 30 products, which is exactly 60. After 29 units they have packed only 7 + 4 + 9 + 4 + 4 + 29 = 57, so the answer is 30.
Approach: try each time in increasing order
Two facts make a simple solution possible:
- In
timeunits, a worker who needstunits per product packstime / tproducts, using integer division that drops the fraction. A worker witht = 7packs 4 products in 30 units, not 4.28. - Giving the workers more time never reduces the number of products. The total only goes up or stays the same as
timegrows.
Together these mean the first time at which the total reaches k is the answer. So the lesson starts at time 0 and adds one unit at a time, asking "have we packed k yet?" after each step. This is the brute-force version. Its cost grows with the answer itself, which is why the statement's budget, O(n * k * T), contains T. The follow-up lesson on the same problem shows how to find the time much faster.
Step by step
- Start the clock.
timeis a mutablei32, written0i32so it has the same type ask. - Loop while the total is too small. The condition is
Self::count_products(×, time) < k.Self::reaches the associated function, and×lends the vector as a slice instead of moving it into the call. - Add one unit of time inside the loop with
time += 1;. - Return
timeas the final expression. When the loop ends,timeis the first value for which the total is at leastk. - Write the helper
count_products(times: &[i32], time: i32) -> i32abovemin_time. It borrows the times as a slice. - Make its body one iterator chain.
times.iter().map(|&t| time / t).sum()turns each worker's time into a product count and adds the counts.
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 mut time = 0i32;
while Self::count_products(×, time) < k {
time += 1;
}
time
}
}
The Rust details behind the one-liner:
iter().map(...).sum().iter()yields&i32references. The closure pattern|&t|copies each number out of its reference, sotime / tdivides two plaini32values. Integer division in Rust truncates toward zero, which for positive numbers is the "integer part" the problem needs.- Why
sum()knows its type. It can add up several number types, and the function's return type,i32, tells it which one. The line has no semicolon, so it is the return value. - Slices as parameters. A
&[i32]parameter accepts a borrowed vector, somin_timecan call the helper many times without cloning or giving uptimes. - Division by zero. If a worker's time were 0,
time / twould panic at run time. The problem assumes every time is positive. - Overflow. The lessons build with optimizations, so
i32arithmetic wraps silently on overflow; a debug build panics instead. A very large total could in principle overflow the sum, but it needs inputs far beyond this lesson's size.
Complexity
Time: O(n * answer). Each call to count_products touches all n workers, and the loop makes one call per time unit until the answer is reached. If the answer is T, that is n * T divisions. In the example, the total is computed for the times 0 to 30, 31 calls over 6 workers each. The answer can be as large as the fastest worker's time multiplied by k, which is what makes this approach slow for big inputs.
Space: O(1). The helper borrows the vector, and only a few integers are stored.
Edge cases and common mistakes
- One worker.
times = [5]withk = 1returns 5: at time 4 the worker has packed nothing, and at time 5 one product. k = 0. The loop condition is false at once, so the function returns 0.- Unfinished products don't count. With
times = [2, 3]andk = 7the answer is 9: at that time the workers pack 4 and 3 products. At time 8 they have packed 4 + 2 = 6. - Using floating-point division. Fractions of a product don't count.
time / tmust be integer division. - Returning the time before the check. The loop must run while the total is less than
k, so that it stops at the first time that reaches it.
Testing
times = [4, 7, 3, 6, 7, 1],k = 60gives30.times = [5],k = 1gives5.times = [2, 3],k = 7gives9.times = [5],k = 0gives0.
