Problem overview
The function minTime receives a slice times, where times[i] is the number of time units worker i needs to pack one product, and a number k. All workers work at the same time, each at their own steady pace. The function returns the smallest amount of time in which 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 adds up to exactly 60. In 29 units they pack only 7 + 4 + 9 + 4 + 4 + 29 = 57, which is not enough.
The statement allows O(n * log(k * T)) time and O(1) extra space, where T is the largest per-product time. The logarithm hints that the answer itself is found by binary search.
Approach: binary search on the answer
It is hard to compute the best time directly, but it is easy to check a time. Given availableTime, a worker who needs t units per product packs availableTime / t products (whole products only), and the total over all workers is a simple sum.
More time never produces fewer products. So the answer has a clean shape: times below some threshold pack fewer than k products, and every time from the threshold up packs at least k. The threshold is the answer, and binary search finds it by testing middle values and discarding half of the candidate times at each step.
The search range needs two ends. The lower end is 1: at least one unit is needed to pack anything. The upper end is the fastest worker's time multiplied by k, because that worker alone packs k products in minValue * k units, so the true answer can't be larger.
The search is on the answer, not on an index of the slice. Each test costs O(n) to add up the workers, and the range has about k * T values, so there are about log(k * T) tests: O(n * log(k * T)) in all.
Step by step
- Find the fastest worker. Start
minValueattimes[0], then range overtimesand take the smaller of the current minimum and eachworkerTime. - Set the search range with
left, right := 1, minValue*k. - Prepare
answer, starting at 0. It will hold the smallest time found so far that is enough. - Loop while
left <= right. Go has nowhile, so the loop is aforwith only a condition. - Pick the middle time,
left + (right-left)/2. - Check it with the helper
countProducts. If the workers pack fewer thankproducts inmiddleunits, the time is too short:left = middle + 1. - Otherwise the time is enough. Store it in
answerbefore shrinking, then try for something shorter withright = middle - 1. - Return
answerafter the loop. - Write
countProducts(times, availableTime). Startproductsat 0, range overtimes, and addavailableTime / workerTimefor each worker. Integer division drops the fraction, which is exactly "only whole products count". Returnproducts.
The solution in Go
func minTime(times []int, k int) int {
minValue := times[0]
for _, workerTime := range times {
minValue = min(minValue, workerTime)
}
left, right := 1, minValue*k
answer := 0
for left <= right {
middle := left + (right-left)/2
if countProducts(times, middle) < k {
left = middle + 1
} else {
answer = middle
right = middle - 1
}
}
return answer
}
func countProducts(times []int, availableTime int) int {
products := 0
for _, workerTime := range times {
products += availableTime / workerTime
}
return products
}
Trace on times = [4, 7, 3, 6, 7, 1], k = 60: minValue is 1, so the range is 1 to 60. The first middle is 30, which packs 60 products, enough, so answer = 30 and the range becomes 1 to 29. The next middle is 15, which is too short, and the search continues in 16 to 29. It keeps finding middles below 30 that are too short, and the loop ends with answer still 30.
Go details in this code
- Built-in
min. Since Go 1.21minandmaxare part of the language and work on numbers without any import. - Integer division.
availableTime / workerTimetruncates toward zero. Both operands are positive here, so this is rounding down, which is the number of whole products. - The blank identifier.
for _, workerTime := range timesdiscards the index, because Go rejects declared variables that are unused. - Division by zero. A worker time of 0 would make an integer division panic at run time. The lesson's inputs have positive times.
- Tabs or spaces. Go code is normally indented with tabs and formatted by
gofmt, but the compiler accepts either.
Complexity
Time: O(n * log(k * T)). The search range has at most minValue * k values, so the loop runs about log₂(minValue * k) times. Each iteration calls countProducts, which visits all n workers. Finding the minimum adds one more pass of O(n).
Space: O(1). A handful of integers.
Edge cases and common mistakes
- Remembering the answer. The search can finish on a middle that was too short, so the last good middle is saved in
answeras it is found. Returningleftormiddlewould be fragile. - One worker. For
times = [5]andk = 3the range is 1 to 15 and the answer is 15. - Whole products only. At 29 units the worker with time 7 packs 4 products, not 4.14. Using floating-point division would overcount.
- Too small an upper bound. If
rightwere smaller than the answer, the search would never see it. The fastest worker's time timeskis always enough. - Starting the range at 0. It is harmless for correctness here but wastes a step, and 0 time packs nothing.
- Several workers with the same time. Each is counted separately, as in the example where two workers need 7 units.
- Large products.
minValue*kand the totals are plainintvalues (64 bits), and only wrap around for inputs far beyond what the lesson uses.
Testing
[4, 7, 3, 6, 7, 1],60gives 30.[5],3gives 15.[2, 3],1gives 2.