Problem overview
The method minTime receives an Array[Int] named times, where times(w) is the number of time units worker w needs to pack one product, and an Int named K. All workers pack at the same time. The method returns the smallest amount of time in which, together, they 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 exactly 60. After 29 units they have packed only 7 + 4 + 9 + 4 + 4 + 29 = 57. So the answer is 30.
Approach: try 0, 1, 2, ... until enough is packed
A worker who needs t units per product packs time / t products in time units, using integer division, because a half-finished product doesn't count. Adding that up over all workers gives the total for a given time.
That total never decreases when the time grows. So the set of times that are long enough starts at some point and continues forever, and the answer is the first time at which the total reaches K. The simplest way to find it is to start at 0 and add one unit at a time until the total is large enough. This lesson uses that direct search. A faster version, which halves a range of candidate times instead of counting up, is a separate lesson on the same problem.
Step by step
- Write a helper
countProducts(times, time)that returns the total number of products packed intimeunits. - In it, start a
var productsat0. For eachtintimes, addtime / t. Returnproducts. - In
minTime, start avar timeat0. - Loop while
countProducts(times, time) < K, adding one unit withtime += 1each round. - When the loop stops, the total has just reached
K, and because the loop went through the times in order, no smaller time worked. Returntime.
The solution in Scala
class Solution {
def countProducts(times: Array[Int], time: Int): Int = {
var products = 0
for (t <- times) {
products += time / t
}
products
}
def minTime(times: Array[Int], K: Int): Int = {
var time = 0
while (countProducts(times, time) < K) {
time += 1
}
time
}
}
Scala details
Scala has no ++ operator, so you add one with time += 1. Both products and time change during the work, so they are vars. A val cannot be reassigned.
for (t <- times) loops over the values of the array, without indices. Read <- as "in".
The last expression of a method is its result, so each method simply ends with the name of the variable to return: products and time. No return keyword is needed.
Dividing two Ints discards the fractional part: 29 / 7 is 4 and 29 / 6 is 4. That is exactly the "whole products only" rule, so no conversion is needed.
A smaller trace
Take times = [2, 5] and K = 7. At time 0 and 1 nobody has finished a product, so the total is 0. At time 2 the first worker has packed 1, at time 4 it has packed 2, and at time 5 the second worker adds 1, so the total is 3. At time 9 the total is 4 + 1 = 5, which is still below 7. At time 10 it jumps to 5 + 2 = 7, the loop condition becomes false, and minTime returns 10.
Complexity
Each call to countProducts takes O(n) time, where n is the number of workers. The loop calls it once for each time value from 0 up to the answer T, so the total is O(n * T). The answer cannot exceed min(times) * K, because the fastest worker alone packs K products in that time. When K is large, this is slow, which is the reason for the binary search version.
The extra space is O(1): two integers in minTime and one in the helper.
Edge cases and common mistakes
- K is zero. At time 0 the total is 0, which is not less than 0, so the loop never runs and the answer is 0.
- One worker. With
times = [5]andK = 1the total stays 0 until time 5, so the answer is 5. In general the answer is a multiple of some worker's time, because the total only grows at those moments. - A worker time of 0.
time / twitht = 0throws anArithmeticException("/ by zero"). The problem assumes every worker needs at least one unit. - Mixing up time and products. The result is the time at which the total first reaches
K, not the number of products. Packing more thanKis fine: withtimes = [2, 5]andK = 7the answer is 10, where the workers have packed 5 + 2 = 7. - Stopping one step too early or late. Return
timeafter the loop, nottime - 1ortime + 1. The condition is "total is less thanK", so the loop leaves with the first time that is good enough. - Using floating-point division. Converting to
Doublewould count fractions of a product and give an answer that is too small.
Testing
[4, 7, 3, 6, 7, 1]withK = 60gives 30; at time 29 the helper returns 57, and at time 30 it returns 60.[5]withK = 1gives 5.[2, 5]withK = 7gives 10.[3, 3]withK = 0gives 0.
