FastPrep
Problem · Array

Get Max Efficiency

Learn this problem
● HardSalesforce logoSalesforceFULLTIMEOA
See Salesforce hiring insights

Problem statement

The manager oversees a set of n servers, each with a designated upgrade capacity represented by the array element capacity[i]. The goal is to create precisely k upgrade batches, where the number of servers in the ith batch is represented by the array element numServers[i] where 0 ≤ i < n.

The efficiency of an upgrade batch is determined by the difference between the maximum and minimum upgrade capacities of the servers within that batch. The manager's objective is to allocate servers to the upgrade batches in a way that maximizes the sum of efficiencies across all k batches. The task is to find the maximum sum of efficiency.

Note: Each server must be assigned to exactly one upgrade batch.

Function

getMaxEfficiency(capacity: int[], numServers: int[]) → long

Complete the function getMaxEfficiency in the editor below.

getMaxEfficiency takes the following parameters:

  1. int capacity[n]: the upgrade capacity of each server
  2. int numServers[k]: the number of servers in each upgrade batch

Returns

long: the maximum possible sum of efficiency of k upgrade batches

Examples

Example 1

capacity = [3, 6, 1, 2]numServers = [1, 3]return = 5

One of the optimal ways is:

  • Batch 1 takes the first server. Therefore, the efficiency of the batch = 3 - 3 = 0
  • Batch 2 takes the servers at indices 1, 2, and 3. The efficiency of the batch = 6 - 1 = 5
Hence, the sum of efficiencies is 0 + 5 = 5.

Example 2

capacity = [1, 2, 3, 4]numServers = [4]return = 3

Since there is only one batch to upgrade all the servers, the efficiency of the batch is 4 - 1 = 3. Hence, the sum of efficiencies of all the batches (which is 1) is 3.

Example 3

capacity = [4, 2, 1]numServers = [1, 1, 1]return = 0

Since the size of each server upgrade batch is 1, all 3 servers are upgraded in different batches, and the efficiency of each batch is 0. Hence, the sum of efficiencies is 0.

Constraints

  • 1 ≤ n ≤ 2x10^5
  • 1 ≤ k ≤ n
  • 1 ≤ capacity[i] ≤ 10^9
  • 1 ≤ numServers[i] ≤ n
  • Σ numServers[i] = n

More Salesforce problems

drafts saved locally
public long getMaxEfficiency(int[] capacity, int[] numServers) {
  // write your code here
}
capacity[3, 6, 1, 2]
numServers[1, 3]
expected5
checking account