FastPrep
Problem · Greedy

Maximize Machine Strength Sum

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

You are given n machines, each with at least two power units. The power units are represented by machinePowers, where machinePowers[i] contains the power values for the i-th machine.

The strength of a machine is the minimum power among all power units currently in that machine.

You may perform the following operation any number of times:

  • Select an unmarked machine.
  • Transfer exactly one power unit from that machine to any other machine.
  • Mark the selected machine. A marked machine cannot be selected again, but it may still receive power units.

Return the maximum possible sum of strengths of all machines after performing operations optimally.

Function

maximizeMachineStrengthSum(machinePowers: int[][]) → long

Examples

Example 1

machinePowers = [[2,7,4],[2,4,3]]return = 6

Move the power unit 2 from the first machine to the second. The strengths become 4 and 2.

Constraints

  • 1 <= machinePowers.length
  • 2 <= machinePowers[i].length
  • The total number of power units is at most 2 * 10^5.

More Amazon problems

drafts saved locally
public long maximizeMachineStrengthSum(int[][] machinePowers) {
  // write your code here
}
machinePowers[[2,7,4],[2,4,3]]
expected6
checking account