FastPrepFastPrep
Problem Brief

Get Max Efficiency

FULLTIMEOA

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 Description

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

1Example 1

Input
capacity = [3, 6, 1, 2], numServers = [1, 3]
Output
5
Explanation

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.

2Example 2

Input
capacity = [1, 2, 3, 4], numServers = [4]
Output
3
Explanation

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.

3Example 3

Input
capacity = [4, 2, 1], numServers = [1, 1, 1]
Output
0
Explanation

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

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 2x10^5
  • 1 ≤ k ≤ n
  • 1 ≤ capacity[i] ≤ 10^9
  • 1 ≤ numServers[i] ≤ n
  • Σ numServers[i] = n
public long getMaxEfficiency(int[] capacity, int[] numServers) {
  // write your code here
}
Input

capacity

[3, 6, 1, 2]

numServers

[1, 3]

Output

5

Sign in to submit your solution.