Minimum Buckets and Smallest Maximum Water Level
Google● MediumFULLTIMEPHONE SCREENProblem statement
Every bucket has the same positive capacity. You have originalWater liters of infinitely divisible water. First, use as few buckets as possible, then among those plans minimize the largest amount in any bucket.
In the follow-up, addedWater liters are added. All of the added water must be placed in bucket 0. Original water may also be placed in bucket 0; other buckets may contain only original water. Apply the same priorities: minimize the number of buckets first, then the largest fill. The added water is no more than one bucket capacity.
Return [baseCount, baseMinMax, followCount, followMinMax] as a double[]. Counts are exact integer-valued doubles. Maximum fills may be fractional; answers within relative or absolute error 1e-7 are accepted.
Function
minimumBucketPlan(capacity: int, originalWater: int, addedWater: int) → double[]Examples
Example 1
capacity = 4originalWater = 5addedWater = 3return = [2.0,2.5,2.0,4.0]Initially two buckets suffice and equal fills of 2.5 minimize the maximum. With eight liters total, two full buckets suffice; the first contains all three added liters plus one original liter.
Example 2
capacity = 10originalWater = 2addedWater = 9return = [1.0,2.0,2.0,9.0]One bucket holds the original two liters. After adding nine liters, two buckets are needed. The first can hold the nine added liters and the second the original two, so the maximum is 9.
Example 3
capacity = 5originalWater = 1addedWater = 5return = [1.0,1.0,2.0,5.0]The follow-up needs two buckets because the first is filled by the five added liters and the original liter goes elsewhere.
Constraints
1 <= capacity <= 1000000.1 <= originalWater <= 1000000.0 <= addedWater <= capacity.- Water is infinitely divisible and may be allocated in arbitrary nonnegative real quantities without exceeding any bucket capacity.