Maximum System Memory Capacity

Maximum System Memory Capacity is an Amazon interview problem involving arrays, greedy algorithms, and sorting. Developers optimize cloud system memory by pairing primary and backup servers under specific constraints.[1][3]

Problem Statement

There are n servers with memory capacities given in array memory[i]. The system requires an even number of servers (2x total), split equally into x primary and x backup servers. Each primary server P must pair with a backup server B where B's memory is strictly greater than P's memory (> P). The goal is to maximize the sum of all primary servers' memories, possibly discarding servers (especially if n is odd) to achieve a valid even-sized configuration.[3][1]

Key Examples

• Input: n = 5, memory =[2][4][1][3] Output: 4
  Explanation: Discard the server with 1 (smallest). Use: primaries =, backups = (2<3 and 2<4). Sum = 4. Other subsets yield ≤4.[4][1][2][3]

• Input: n = 3 (odd case implied), memory example leading to output 1
  Explanation: Discard one to get even count; pair to maximize primaries while ensuring backups > primaries each.[3]

Constraints

• 2 ≤ n ≤ 2×10^5
• 1 ≤ memory[i] ≤ 10^9
  n can be odd, requiring discard of at least one server. Time complexity should be O(n log n) via sorting and greedy pairing.[1][3]