FastPrepMaximum Reservoir Power

Maximum Reservoir Power

Wells Fargo logoWells Fargo● MediumFULLTIMEOA
Learn

Problem statement

A hydropower plant is connected to n water reservoirs. Opening reservoir i generates capacity[i] units of electricity.

Some pairs of reservoirs conflict and cannot be opened together. The undirected conflict graph is guaranteed to be a forest.

Choose a set of reservoirs with no conflicting pair and return the maximum total electricity they can generate.

The arrays conflictFrom and conflictTo have equal length. Their values are 1-indexed reservoir numbers, and pair j connects conflictFrom[j] with conflictTo[j].

Function

maxReservoirPower(capacity: int[], conflictFrom: int[], conflictTo: int[]) → long

Examples

Example 1

capacity = [5,1,4,3]conflictFrom = [1,2,3]conflictTo = [2,3,4]return = 9

Open reservoirs 1 and 3 for 5 + 4 = 9 units.

Example 2

capacity = [10,1,1,10]conflictFrom = [1,2,3]conflictTo = [2,3,4]return = 20

Reservoirs 1 and 4 are not adjacent, so both can be opened for 20 units.

Example 3

capacity = [8,5,6,4,7,3]conflictFrom = [1,2,4]conflictTo = [2,3,5]return = 24

Choose reservoirs 1 and 3 from the first component, reservoir 5 from the second component, and isolated reservoir 6: 8 + 6 + 7 + 3 = 24.

Constraints

  • 1 <= capacity.length <= 10^5.
  • 1 <= capacity[i] <= 10^5.
  • conflictFrom.length == conflictTo.length.
  • 0 <= conflictFrom.length <= capacity.length - 1.
  • Every conflict endpoint is between 1 and capacity.length, endpoints in a pair are different, and pairs are unique.
  • The conflict graph is a forest.

More Wells Fargo problems

See Wells Fargo hiring insights
public long maxReservoirPower(int[] capacity, int[] conflictFrom, int[] conflictTo) {
  // write your code here
}
capacity[5,1,4,3]
conflictFrom[1,2,3]
conflictTo[2,3,4]
expected9
Checking account…