Problem overview
A factory has several workers, and times[i] is the number of time units worker i needs to pack one product. All of them work at the same time without stopping. The method minTime receives times and a number K, and returns the smallest amount of time in which the workers together pack at least K products.
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 60 in total. After 29 units they have packed only 57, so the answer is 30.
The statement allows O(n * k * T) time: this is the simple version, which checks the times one after another. A faster binary-search version is the next lesson on the same problem.
Approach: try 0, 1, 2, ... until enough is packed
A worker who needs t units per product finishes time / t products in time units, rounded down, because an unfinished product doesn't count. Adding this up over all workers gives the number of products packed by a given time.
That total never decreases as time grows. So the answer is the first time at which the total reaches K: start at 0 and add one unit at a time until the total is large enough. Counting the total is a separate job, so it goes into a helper, countProducts.
Checking the example by hand: at time 3 the workers pack 0 + 0 + 1 + 0 + 0 + 3 = 4 products, at time 10 they pack 2 + 1 + 3 + 1 + 1 + 10 = 18, and the loop keeps going until the total first reaches 60 at time 30. At time 29 it is 7 + 4 + 9 + 4 + 4 + 29 = 57, still short.
Step by step
- Declare
timewithvar, starting at 0, because the loop changes it. - Loop while
countProducts(times, time) < K. As long as too few products are packed, more time is needed. - Add one unit with
time += 1. Swift has no++operator. - Return
time. It is the first time at whichKproducts are packed. - Write the helper above
minTimeasfunc countProducts(_ times: [Int], _ time: Int) -> Int. The_labels allow the callcountProducts(times, time). - Start
productsat 0 withvar. - Loop over the values of
timeswithfor t in times. - Add
time / ttoproducts. Dividing twoInts drops the fraction, which is the rounding we want. - Return
products.
The solution in Swift
class Solution {
func countProducts(_ times: [Int], _ time: Int) -> Int {
var products = 0
for t in times {
products += time / t
}
return products
}
func minTime(_ times: [Int], _ K: Int) -> Int {
var time = 0
while countProducts(times, time) < K {
time += 1
}
return time
}
}
The Swift details worth a closer look:
- Integer division. With two
Intoperands,/truncates toward zero, so7 / 2is 3. For the non-negative numbers here, that is the same as rounding down. - Division by zero traps. If a value in
timeswere 0,time / twould stop the program. The lesson's workers always need at least one unit per product. - No
++. Swift removed the increment operator, sotime += 1is the idiom. - Parameter named
K. Swift allows a capital letter in a parameter name. The name is only a convention, and the lesson keepsKas in the statement.
Complexity
The cost depends on how large the answer is, not only on the number of workers. For example, one worker who needs 1,000 units per product and a K of 1,000,000 give an answer of 1,000,000,000, so the loop runs a billion times, each time calling countProducts.
Let n be the number of workers and T the answer.
Time: O(n * T). Each of the T + 1 checks of the loop condition calls countProducts, which visits every worker once. The statement's bound O(n * k * T) is a looser limit; the O(n * T) count is what this code does. Since the answer grows with K, a large K with slow workers makes the loop long. This is why the next lesson searches for the time with a binary search.
Space: O(1). Only a few integers are stored.
Edge cases and common mistakes
Kis 0. The loop condition is false at once, and the method returns 0.- One worker. With
times = [5]andK = 3the answer is 15, three products at 5 units each. - A product that is not finished. At time 29 the worker who needs 7 units has packed 4 products, since 29 / 7 is 4 after truncation. Rounding up would count products still in progress and give a time that is too small.
- Returning the total. The method returns a time, not a count of products.
- Starting the time at 1. With
K = 0the answer would be wrong, because 0 already works.
Testing
times = [4, 7, 3, 6, 7, 1],K = 60gives30.times = [5],K = 3gives15.times = [3, 3],K = 1gives3.times = [3, 3],K = 0gives0.
