Maximize total cluster throughput from median-of-three servers

Count first. With n servers we can build k = n // 3 clusters. Throughputs are non-negative, so building all k clusters never lowers the total. The only real question is who goes with whom.

Brute force. Try every way to split the servers into k triples and keep the best sum of medians. The count of partitions grows faster than exponentially, so this only works for n ≤ 9 or so. It is still worth saying out loud, and it is the oracle for the tests below.

Key idea. A median needs one partner at least as large (the cluster's maximum) and one partner no larger (the cluster's minimum). Large partners are the scarce resource: every big value spent as a maximum is a big value that does not count. Small partners cost nothing, because the minimum of a cluster never counts.

Greedy. Sort descending into b. Pair the values two at a time from the top: (b[0], b[1]), (b[2], b[3]), ... For each pair, the larger one is the maximum, the smaller one is the median. Give each cluster one of the k smallest values as its minimum. The answer is b[1] + b[3] + ... + b[2k - 1].

Why it is optimal (upper bound). Take any valid grouping and sort its medians descending: m_1 ≥ m_2 ≥ ... ≥ m_k. The clusters holding m_1 .. m_i each contain the median and an element at least as large, which is 2i distinct elements all ≥ m_i. So at least 2i values in the array are ≥ m_i, which means m_i ≤ b[2i - 1]. Summing over i gives total ≤ b[1] + b[3] + ... + b[2k - 1], and the greedy reaches that bound.

Why the greedy is valid. It uses the top 2k values as maxima and medians and the bottom k values as minima. Since 3k ≤ n, these sets do not overlap, and each minimum is ≤ every value in the top 2k, so each chosen median really is the middle value of its cluster. Leftover servers (n mod 3) sit in the middle and stay unused.

Invariant. After the descending sort, position 2i - 1 holds the best possible i-th largest median, and the greedy places a median exactly there for every i.

from itertools import permutations


def max_throughput(host_throughput: list[int]) -> int:
    """Sum of medians over n // 3 clusters of three servers. O(n log n)."""
    b = sorted(host_throughput, reverse=True)
    k = len(b) // 3
    # Medians sit at descending positions 1, 3, 5, ..., 2k - 1.
    return sum(b[1:2 * k:2])


def build_clusters(host_throughput: list[int]) -> list[tuple[int, int, int]]:
    """Return the actual clusters as (max, median, min) value triples."""
    b = sorted(host_throughput, reverse=True)
    k = len(b) // 3
    smallest = b[len(b) - k:]  # the k smallest values serve as minima
    return [(b[2 * i], b[2 * i + 1], smallest[i]) for i in range(k)]


def max_throughput_brute(host_throughput: list[int]) -> int:
    """Oracle for small n: try every ordering, cut it into triples."""
    k = len(host_throughput) // 3
    best = 0
    for perm in permutations(host_throughput):
        total = sum(sorted(perm[3 * i:3 * i + 3])[1] for i in range(k))
        best = max(best, total)
    return best


if __name__ == "__main__":
    import random

    assert max_throughput([4, 6, 3, 5, 4, 5]) == 9  # (6,5,4) and (5,4,3)
    assert max_throughput([2, 3, 4, 3, 4]) == 4      # one cluster, two left over
    assert max_throughput([1, 2]) == 0               # no cluster possible
    assert max_throughput([]) == 0
    assert max_throughput([7, 7, 7]) == 7
    assert max_throughput([1, 1, 1, 9, 9, 9]) == 10
    assert max_throughput([8, 1, 8, 2, 7, 3]) == 11  # not (8,8,7)+(3,2,1)=10
    assert max_throughput([5, 1, 10]) == 5
    assert build_clusters([4, 6, 3, 5, 4, 5]) == [(6, 5, 4), (5, 4, 3)]

    for _ in range(300):
        n = random.randint(0, 8)
        arr = [random.randint(0, 10) for _ in range(n)]
        assert max_throughput(arr) == max_throughput_brute(arr), arr
        clusters = build_clusters(arr)
        assert sum(c[1] for c in clusters) == max_throughput(arr)
        assert all(c[0] >= c[1] >= c[2] for c in clusters)
    print("all tests passed")

• max_throughput: O(n log n) time for the sort, O(n) space for the sorted copy (O(1) extra if sorting in place is allowed).
• build_clusters: same, plus O(k) for the output.
• Brute force: O(n!) time, only for testing.
• With bounded throughput values (say 0..10^4), a counting sort makes the whole thing O(n + V).
• Only the top 2k values matter for the sum, so a selection step (heapq.nlargest(2k, ...) or quickselect) can replace the full sort, though 2k is about 2n/3, so the gain is small.

• [4, 6, 3, 5, 4, 5] → 9. Sorted desc [6, 5, 5, 4, 4, 3]; clusters (6, 5, 4) and (5, 4, 3); medians 5 + 4.
• [2, 3, 4, 3, 4] → 4. One cluster (4, 4, 2); the two 3s are unused.
• [1, 2] → 0. Fewer than three servers, no cluster.
• [] → 0.
• [7, 7, 7] → 7. All equal.
• [8, 1, 8, 2, 7, 3] → 11. Grouping the top three together, (8, 8, 7) and (3, 2, 1), gives only 10; the greedy gives (8, 8, 2) and (7, 3, 1) for 8 + 3.
• [5, 1, 10] → 5. Single cluster; the median is the middle value.
• Large input (n = 2·10^5, values up to 10^9): sum can exceed 32 bits; use a 64-bit type in Java or C++.
• Randomized check against the brute force for n ≤ 8.

1. Clusters of size m (odd), median throughput. Each cluster needs h - 1 = (m - 1) / 2 values above its median and (m - 1) / 2 below. Sort descending; medians sit at positions h - 1, 2h - 1, ..., kh - 1 where h = (m + 1) / 2 and k = n // m. The bottom k · (m - 1) / 2 values fill the lower halves. Same exchange argument.
2. Return the clusters, not just the sum. build_clusters above: pair from the top, attach a minimum from the bottom. Mention that any minimum works as long as it comes from the bottom k.
3. Negative throughputs, clusters optional. Now a cluster can hurt. The i-th cluster adds b[2i - 1] in descending order, and these are non-increasing, so take clusters while b[2i - 1] > 0 (the best prefix of a non-increasing sequence). Still O(n log n).
4. Exactly c clusters required (c ≤ n // 3). Use b[1] + b[3] + ... + b[2c - 1] with minima from the bottom c. The upper-bound proof does not change.
5. Servers arrive as a stream and you report the best total after each arrival. An insertion shifts the rank parity of every smaller value, so a plain running sum breaks. Use a segment tree over compressed values where each node stores its count and the sums of its values at even and odd descending rank within the node; merging swaps the right child's parities when the left count is odd. Query the odd-rank sum over the top 2k values in O(log n) per update.

Mid-level (L4)

• Sees that n // 3 clusters is the count and that leftovers never matter.
• Finds the sort-descending, take-every-other-from-the-top pattern, possibly from small examples.
• Writes correct code with the slice b[1:2k:2] or an equivalent loop, and handles n < 3.

Senior (L5)

• Explains why the smallest values are the right minima and why pairing big values together is not wasteful but necessary.
• Gives the upper-bound argument (m_i ≤ b[2i - 1]) or a clean exchange argument, not just "it works on examples".
• Calls out overflow on large inputs and tests with a brute-force oracle.

Staff (L6+)

• Generalizes to cluster size m and to other order statistics in one framework.
• Handles the negative-value and streaming variants, with clear complexity trade-offs.
• Relates it to known problems (the "maximum coins from piles of three" pattern) and discusses when a counting sort or selection beats a full sort.