Maximum Production Within Power
Learn this problem
Zomato / EternalFULLTIMEOAProblem statement
You are given parallel integer arrays power and quantity. Machine i requires power[i] units of power and produces quantity[i] units.
Order the machines by increasing power requirement. Machines with equal power requirements keep their original input order. Starting from the beginning of this order, select machines while adding the next machine would keep cumulative power at most maxPower. Stop before the first machine that would exceed the limit.
Return the total quantity produced by the selected prefix as a 64-bit integer.
Function
maximumProduction(power: int[], quantity: int[], maxPower: long) → longExamples
Example 1
power = [4,2,5,1]quantity = [40,20,50,10]maxPower = 7return = 70The increasing-power order is machine indices [3,1,0,2]. The first three machines consume 1 + 2 + 4 = 7 power and produce 10 + 20 + 40 = 70 units. Adding the last machine would exceed the limit.
Example 2
power = [2,2,5]quantity = [9,100,1]maxPower = 2return = 9The first two machines tie on power and therefore keep input order. The first machine is selected, but adding the second would make cumulative power 4, so the selected prefix produces 9 units.
Constraints
1 <= power.length == quantity.length <= 2000001 <= power[i], quantity[i] <= 10000000001 <= maxPower <= 10^18- The returned quantity fits in a signed 64-bit integer.