Schedule Batch Difference

Given n servers with their capacity, we need to schedule k batches. Input: n (number of servers) Capacity array of length n k (batches) numServers array of length k where numServers[i] = number of servers to be included in i-th batch Output: For each batch calculate difference between maximum and minimum server capacity, sum it over for all k batches and return it.

Constraints

• Summation of numServers[i] == n
• n ≤ 1e6
• k ≤ n

Example 1

Input:

n = 4
capacity = [1, 2, 3, 4]
k = 1
numServers = [4]

Output:

3

Explanation: Heads up This and the following 2 expanations are not from the official There is only one batch, and it includes all servers. The difference between the maximum and minimum server capacity is 4 - 1 = 3.

Example 2

Input:

n = 4
capacity = [1, 2, 3, 4]
k = 4
numServers = [1, 1, 1, 1]

Output:

0

Explanation: Each batch includes only one server, so the difference between the maximum and minimum server capacity for each batch is 0. The total sum is 0.

Example 3

Input:

n = 4
capacity = [1, 2, 3, 4]
k = 2
numServers = [2, 2]

Output:

4

Explanation: The first batch can include servers with capacities 1 and 4, and the second batch can include servers with capacities 2 and 3. The difference for the first batch is 4 - 1 = 3, and for the second batch is 3 - 2 = 1. The total sum is 3 + 1 = 4.