Maximize total cluster throughput from median-of-three servers

You manage a fleet of host servers. hostThroughput[i] is the throughput of server i (a non-negative integer).

Group servers into clusters of exactly three distinct servers. Build as many clusters as possible, which is n // 3. A server can be in at most one cluster, and servers left over are not used.

A cluster's throughput is the median of its three servers' throughputs (the middle value after sorting the three). Return the largest possible sum of cluster throughputs.

def max_throughput(host_throughput: list[int]) -> int: ...

Constraints

• 0 <= n <= 2 * 10^5
• 0 <= hostThroughput[i] <= 10^9
• The answer can exceed 32 bits.

Example 1

Input:  [4, 6, 3, 5, 4, 5]
Output: 9

Two clusters: {6, 5, 4} has median 5 and {5, 4, 3} has median 4, so the total is 9. No grouping does better.

Example 2

Input:  [8, 1, 8, 2, 7, 3]
Output: 11

Grouping the three largest together, {8, 8, 7} and {3, 2, 1}, gives only 8 + 2 = 10. The grouping {8, 8, 1} and {7, 3, 2} gives 8 + 3 = 11, which is the best.

If n < 3, return 0.