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 workers pack at once. The method returns the smallest time after which they have packed at least K products between them.
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 is exactly 60. In 29 units they pack only 7 + 4 + 9 + 4 + 4 + 29 = 57.
A worker who needs t units per product packs time / t whole products in time units. With int operands, C# division already drops the fraction.
The lesson asks for O(n * log(k * T)) time and O(1) extra space. Trying every time from 0 upward would be too slow when the answer is large.
Approach: binary search on the answer
The number of packed products never decreases as the time grows. So the times split into two groups: the short ones, which pack fewer than K products, and the long ones, which pack at least K. The answer is the first time of the second group. A sorted split like this is exactly what binary search needs, even though there is no array of times to look into. The search runs over the numbers 1, 2, 3, ... themselves, and the helper CountProducts plays the role of the comparison.
Two bounds are needed. The lower one is 1. For the upper one, the fastest worker alone packs K products in minValue * K units, so the workers together never need more than that. The answer is therefore somewhere in [1, minValue * K].
On each step, take the middle time mid and count the products:
- If the count is below
K, thenmidis too short, and so is everything below it. Search the upper half. - Otherwise
midworks, but a smaller time might too. Remembermidand keep searching the lower half.
For the example, the bounds are 1 and 1 * 60 = 60. The search takes six rounds of halving and ends with time = 30, the same answer as the brute-force version in the previous lesson.
Step by step
- Find the fastest worker. Start
minValueattimes[0]and lower it withMath.Min(minValue, t)in aforeachloop. - Set the bounds. Declare
left = 1andright = minValue * Kin one statement. - Declare
timeas0. It will hold the smallest good time found so far. - Loop while
left <= right. - Compute
midas(left + right) / 2. Integer division drops the fraction. - If
CountProducts(times, mid) < K, the time is too short, so setleft = mid + 1. - Otherwise record
time = midfirst, then setright = mid - 1to look for something shorter. Record before shrinking: the loop may end on amidthat was too short, so the last good one has to be saved. - Return
timeafter the loop. - Write
CountProductsaboveMinTime, withproductsstarting at0. - Loop over the workers with
foreach (int t in times)and addtime / ttoproducts. - 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 minValue = times[0];
foreach (int t in times) {
minValue = Math.Min(minValue, t);
}
int left = 1, right = minValue * K;
int time = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (CountProducts(times, mid) < K) {
left = mid + 1;
} else {
time = mid;
right = mid - 1;
}
}
return time;
}
}
C# details worth knowing
- Two variables in one declaration.
int left = 1, right = minValue * K;declares both asint, and the second initializer can useminValue, which exists already. Math.Min. It lives in theSystemnamespace and returns the smaller of two numbers. Names in C# are case-sensitive, soMath.mindoes not exist.intoverflow is silent. C# does not stop on overflow by default. IfminValue * Kexceeds about 2.1 billion, the product wraps around to a wrong number. For example, withtimes = {1000000}andK = 5000, the true bound is 5,000,000,000, which doesn't fit in anint. The wrapped bound is705032704, and this solution then returns0, which is wrong. Computing the bound as alongavoids this. Likewise,(left + right) / 2can overflow when both bounds are large, andleft + (right - left) / 2is the safe form. Within the sizes this lesson uses, the plain versions are fine.- Dividing by a worker's time. A time of
0would throw aDivideByZeroException, so the problem assumes positive times.
Complexity
The search range has about minValue * K values, and each iteration halves it, so the loop runs about log(minValue * K) times. Each iteration calls CountProducts, which is a pass over the n workers. The total time is O(n * log(k * T)), where T stands for the size of a worker's time. The first pass that finds the fastest worker costs O(n) and doesn't change the total.
The solution keeps only a handful of int variables, so the extra space is O(1).
Edge cases and common mistakes
- Forgetting to record
time. The loop can finish on amidthat was too short, so the result has to be the last goodmidsaved in theelsebranch, notleftorright. - Setting
right = midorleft = mid. With theleft <= rightloop, each branch must move pastmid(mid + 1ormid - 1), or the search can repeat the samemidforever. - Using
<=in the count test. A count of exactlyKis good enough, so the comparison is a strict<. - A too-small upper bound. Starting
rightbelow the true answer makes the search return a wrong time. The fastest worker alone is a bound that is always large enough. - One worker. For
times = {5}andK = 1, the bounds are1and5, and the method returns5.
Testing
| times | K | result |
|---|---|---|
{4, 7, 3, 6, 7, 1} | 60 | 30 |
{5} | 1 | 5 |
{3, 3} | 1 | 3 |