Maximum Server Health Sum

Overview

The objective is to select at most k distinct server types to maximize the total health score. A key constraint is that if we select a server type, we must include all servers associated with that type.

The problem can be broken down into three logical steps:

1. Group and Sum: Aggregate the total health for each unique server type.
2. Filter: Since we want to maximize the sum, we should ignore any server type whose total aggregated health is negative or zero, as adding them would not help (or would even hurt) our total.
3. Selection: Sort the positive aggregated health scores in descending order and pick the top k (or fewer, if fewer than k positive types exist).

Brute Force

A brute force approach would involve generating every possible combination of server types up to size k, calculating the sum for each combination, and keeping track of the maximum. However, with up to $10^5$ servers and many distinct types, the number of combinations would be astronomically high.

A slightly more "informed" brute force would be to aggregate the sums using a dictionary and then use nested loops to find the best k types, but even this is inefficient compared to sorting.

Implementation

def max_server_health(health: list[int], serverType: list[int], k: int) -> int:
    # Aggregate health by type
    type_sums = {}
    for h, t in zip(health, serverType):
        type_sums[t] = type_sums.get(t, 0) + h
    
    # Extract sums into a list
    all_sums = list(type_sums.values())
    
    # Brute force selection: sort and pick top k
    # Sorting is actually the bottleneck here, but for brute force 
    # explanation, we treat the aggregation and simple selection logic.
    all_sums.sort(reverse=True)
    
    max_total = 0
    count = 0
    for s in all_sums:
        if count < k and s > 0:
            max_total += s
            count += 1
        else:
            break
            
    return max_total

Time complexity: O(N log N) — Dominated by sorting the distinct server type sums. Space complexity: O(N) — Storing the health sums for each unique server type in a hash map.

Optimal / Best Approach

The optimal approach refines the aggregation and selection process. We use a hash map (dictionary in Python) to calculate the total health for each serverType in a single pass. After calculating these totals, we only care about the values that are greater than zero. We sort these positive totals in descending order and sum the first min(k, len(positive_totals)) values.

Implementation

from collections import defaultdict

def max_server_health(health: list[int], serverType: list[int], k: int) -> int:
    # Use a dictionary to aggregate health sums for each server type
    type_to_health = defaultdict(int)
    for i in range(len(health)):
        type_to_health[serverType[i]] += health[i]
    
    # Filter for types that have a positive total health contribution
    # We only care about positive sums because k is a maximum limit, 
    # not a requirement to pick exactly k.
    positive_sums = [total for total in type_to_health.values() if total > 0]
    
    # Sort sums in descending order to pick the best contributors first
    positive_sums.sort(reverse=True)
    
    # Take the top k positive sums
    return sum(positive_sums[:k])

Time complexity: O(N + M log M) — Where $N$ is the number of servers and $M$ is the number of distinct server types. We iterate through $N$ servers once to build the map, then sort $M$ totals. Space complexity: O(M) — We store the aggregated health sum for each of the $M$ distinct server types.

Why this works

• Aggregation: Since we must take all servers of a chosen type, the "unit" of our decision-making is the total health of that type.
• Greedy Selection: This problem exhibits optimal substructure. To get the maximum total health from k choices, we should always pick the types with the highest individual total health first.
• Handling Negatives: If a server type has a total health of -5, including it will always result in a smaller sum than excluding it. Since the problem allows us to pick at most k types, we are never forced to pick a negative contributor.