Maximize capacity with primary-backup pairing

Q: Maximize capacity with primary-backup pairing

This question evaluates combinatorial optimization and constrained matching skills, focusing on algorithm design, complexity analysis, and resource-allocation reasoning for maximizing aggregate capacity under pairing constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given n servers, where server i has memory capacity memory[i]. A valid system must contain an even number of servers.

If the system contains 2x servers, then:

exactly x servers are designated as primary
exactly x servers are designated as backup
every primary server P must be paired with a distinct backup server B such that memory[B] >= memory[P]

The system memory capacity is defined as the sum of memory capacities of all primary servers.

Task: Given n and the array memory, compute the maximum possible system memory capacity over all valid choices of an even-sized subset of servers and a valid primary/backup pairing.

Complete the function:

maximumCapacity(memory) → returns a 64-bit integer (long)

Constraints:

2 <= n <= 2 * 10^5
memory[i] are integers (assume non-negative)

Notes:

You may choose any even number of servers from the n servers (you do not have to use all servers).
Each server can be used at most once (either primary or backup, or not chosen).

Maximize capacity with primary-backup pairing

Overview

Comments (0)