Maximize capacity with primary-backup pairing

Problem Statement

You are managing a server cluster where each server has a specific capacity. To ensure high availability, you must pair servers into Primary-Backup sets. A pair consists of two distinct servers. The 'capacity' of a pair is defined as the minimum capacity of the two servers in that pair.

Given an array of integers capacities representing the capacity of each server, your goal is to partition all servers into pairs such that the sum of the capacities of all pairs is maximized. Each server can be part of exactly one pair. You are guaranteed that the total number of servers is even.

Function Signature

def maximize_total_capacity(capacities: list[int]) -> int:
    pass

Constraints

• 2 <= len(capacities) <= 10^5
• len(capacities) is always even.
• 1 <= capacities[i] <= 10^4

Examples

Example 1:

• Input: capacities = [1, 4, 2, 3]
• Output: 4
• Explanation: Possible pairings: (1, 2) and (3, 4). Min(1, 2) = 1, Min(3, 4) = 3. Sum = 1 + 3 = 4.

Example 2:

• Input: capacities = [6, 2, 6, 5, 1, 2]
• Output: 9
• Explanation: Pairing (1, 2), (2, 5), (6, 6) gives min values: 1 + 2 + 6 = 9.

Edge Cases

• Arrays with duplicate capacity values.
• Arrays where all capacities are the same.
• Arrays with very large or very small capacity ranges.