Problem overview
MinTime receives an int[] times, where times[i] is how many time units worker i needs to pack one product, and an int K. All the workers pack at the same moment, each at their own pace. The method returns the smallest number of time units after which the workers together have packed at least K products.
In the example, times = {4, 7, 3, 6, 7, 1} and K = 60. After 30 units the workers pack 7, 4, 10, 5, 4 and 30 products, which add up to exactly 60. After 29 units they pack only 7 + 4 + 9 + 4 + 4 + 29 = 57, so 30 is the answer.
A worker who needs t units per product packs time / t whole products in time units, rounding down. Half a product doesn't count.
Approach: try the times in increasing order
The total number of products never decreases as the time grows, because more time can't make anyone pack fewer products. So the first time at which the total reaches K is the answer, and the simplest way to find it is to try 0, 1, 2, ... and stop at the first success.
Counting the products for one candidate time takes one pass over the workers. If the answer is T, the loop makes about T passes of n workers each. This is slow when the answer is large, and the next lesson on this problem replaces the one-by-one search with a binary search on the time. This lesson stays with the straightforward version.
Trace the example up to 29. The count at time 29 is 57, which is below 60, so the loop moves on to 30. At 30 the count is 60, the condition count < K becomes false, and the loop ends with time = 30.
The same observation explains why the loop can stop at the first success. Once the count reaches K at some time, every later time also reaches it, so no later time can be a smaller answer, and no earlier time was good enough or the loop would have stopped there. Without this property, finding the first good time would need a different argument.
Step by step
- Declare
timeas anintstarting at0. It is the candidate being tested. - Loop while
CountProducts(times, time) < K. The helper, written below, returns how many products everyone packs intimeunits. While that count is too low, the candidate is too small. - Add one unit with
time++inside the loop. - Return
timeafter the loop. The loop stops at the first time where the count reachesK. - Declare the helper above
MinTimeaspublic int CountProducts(int[] times, int time). - Start
productsat0. - Loop over the workers with
foreach (int t in times). - Add
time / ttoproducts. Dividing twoints already discards the fractional part, which is the "whole products only" rule. - Return
products.
The solution in C#
class Solution {
public int CountProducts(int[] times, int time) {
int products = 0;
foreach (int t in times) {
products += time / t;
}
return products;
}
public int MinTime(int[] times, int K) {
int time = 0;
while (CountProducts(times, time) < K) {
time++;
}
return time;
}
}
C# details worth knowing
- Integer division truncates. With two
intoperands,29 / 7is4, not4.14. That is exactly the rule for whole products, so noMath.Flooris needed. Casting todoublefirst would give a fraction and break the count. foreach.foreach (int t in times)visits each element in order. It is the natural choice when you don't need the index.- Parameter named
time. InCountProducts,timeis the candidate, and inMinTimeit is the local variable that holds it. They are separate variables that happen to share a name. - Zero worker time. A worker with
t = 0would maketime / tthrow aDivideByZeroException. The problem implies that every worker needs a positive time.
Complexity
Each call to CountProducts takes O(n) time, where n is the number of workers. The loop calls it once per candidate time, so if the answer is T, the total is about O(n * T). In the worst case T grows with K, because even the fastest worker needs minTime * K units alone, so the time can grow with K.
The extra space is O(1): a few int variables.
Edge cases and common mistakes
- The starting value. At time
0nobody has packed anything, so0is a safe place to start. IfKis0, the count is never below it and the method returns0without looping. - Returning
time - 1ortime + 1. The loop leavestimeon the first time that works, so return it as is. - Using
<=in the loop condition. That would continue past the first time with exactlyKproducts, and return one unit too many. - Floating-point division. Computing
time / (double)tand adding the results counts fractions of products. Keep the division on integers. - Large inputs. This version steps one unit at a time. If the answer is in the millions, it needs millions of passes over the workers. Binary search on the time fixes that.
Testing
| times | K | result |
|---|---|---|
{4, 7, 3, 6, 7, 1} | 60 | 30 |
{5} | 1 | 5 |
{3, 3} | 1 | 3 |