Problem overview
A factory has several workers, and times[i] is the number of time units worker i needs to pack one product. They all work at the same time. The method minTime receives times and a number K and returns the smallest time in which the workers together pack at least K products.
With 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 + 30 = 60 products, while 29 units give only 57. The statement asks for O(n * log(k * T)) time, where n is the number of workers, k is K and T bounds the time per product, using O(1) extra space.
Approach: binary search on the answer
The simple solution tries 0, 1, 2, ... time units until enough products are packed. That works, but it may take as many steps as the answer is large. The total number of products packed never decreases as time grows. So the times split into two groups: every time below the answer packs fewer than K products, and every time from the answer onward packs at least K. A border between two groups like that can be found with binary search, here over the possible times instead of over array indices.
The search needs a range to start from. The lowest candidate is 1. For the highest, take the fastest worker, who needs minValue units per product: working alone, they pack K products in minValue * K units, and the whole team can only do better. So the answer lies in [1, minValue * K].
Each step tests the middle time mid. If the team packs fewer than K products by then, mid is too short and the search continues above it. Otherwise mid works, so it is saved as the best answer so far, and the search continues below it for something shorter.
On the example the range is 1 to 60, since the fastest worker needs 1 unit. The first middle is 30, which packs exactly 60 products, so 30 is saved and the search continues in 1 to 29. Those times all pack fewer than 60, so left moves up until it passes right, and the saved 30 is returned.
Step by step
- Find the fastest worker. Start
var minValueattimes[0]and, in afor t in timesloop, update it withminValue = min(minValue, t). - Set the bounds:
var left = 1andvar right = minValue * K. - Declare
var time = 0. It keeps the smallest time found so far that packs at leastKproducts. - Loop while
left <= right. - Take the middle:
let mid = (left + right) / 2. Integer division drops the fraction. - If
countProducts(times, mid) < K, thenmidis too short: setleft = mid + 1. - Otherwise record
time = midand then setright = mid - 1to look for a shorter time. The record comes first because the loop may finish on amidthat was too short. - Return
time. - Write the helper
countProducts(_ times: [Int], _ time: Int) -> IntaboveminTime. It startsvar products = 0, loops withfor t in times, addstime / teach time and returnsproducts. Dividing twoInts already drops the fraction, which counts only finished 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 minValue = times[0]
for t in times {
minValue = min(minValue, t)
}
var left = 1
var right = minValue * K
var time = 0
while left <= right {
let mid = (left + right) / 2
if countProducts(times, mid) < K {
left = mid + 1
} else {
time = mid
right = mid - 1
}
}
return time
}
}
The Swift details worth a closer look:
- The global
min.min(minValue, t)is a function from the standard library that returns the smaller of two values. It works becauseIntis comparable. Another way to write the whole loop istimes.min(), which returns an optional, because an empty array has no minimum. - Empty input crashes.
times[0]on an empty array stops the program with an index-out-of-range error. The lesson assumes at least one worker. - Overflow traps.
minValue * Kis a 64-bitIntmultiplication. It can't overflow for realistic values, but if it did, Swift would stop the program instead of wrapping around. - Division truncates.
time / tgives the whole number of finished products, because both operands areInt.
Complexity
Time: O(n * log(k * T)). The search range has about minValue * K values, and the binary search halves it every iteration, so there are about log(minValue * K) iterations. Each iteration calls countProducts, which visits all n workers. Finding minValue costs O(n) once.
Space: O(1). Only a few integers are stored.
Edge cases and common mistakes
- One worker. With
times = [5]andK = 3the range is 1 to 15, and the answer is 15. Kis 0. The upper bound is 0, the loop never runs, and the method returns 0.- Several equally fast workers. For
[3, 3]andK = 1the upper bound is 3, and the answer is 3. Both workers finish a product at the same time. - Not saving
mid. Returningleftorrightinstead of the recordedtimeis easy to get wrong; keep the lastmidthat worked. - Moving past a working
mid. Settingleft = mid + 1whenmidpacks enough would skip the answer. - Using the slowest worker for the upper bound. That is a valid bound but a needlessly large one. The fastest worker gives a tighter bound and the correct one.
Testing
times = [4, 7, 3, 6, 7, 1],K = 60gives30.times = [5],K = 3gives15.times = [3, 3],K = 1gives3.times = [2, 9],K = 1gives2.times = [3, 3],K = 0gives0.
