Maximize Happiness of Selected Children

medium array greedy sorting

Problem

You have n children in a queue; child i has happiness happiness[i]. Select k children over k turns. Each turn, when you pick a child, every child not yet picked loses 1 happiness — but a value never drops below 0. Return the maximum possible sum of the happiness values of the children at the moment you pick each of them.

Inputhappiness = [1, 2, 3], k = 2

Output4

Pick 3 first (turn 0, no penalty) → +3. The rest become [0, 1]. Pick 1 next: it has already dropped by 1 to give 2 − 1 = 1 → +1. Total = 3 + 1 = 4.

happiness (comma-separated)

def maximumHappinessSum(happiness, k):
    happiness.sort(reverse=True)   # largest values first
    total = 0
    for i in range(k):             # i = turn index = penalty so far
        gain = happiness[i] - i    # value after i decrements
        if gain <= 0:
            break                  # rest are 0 too; stop
        total += gain
    return total

function maximumHappinessSum(happiness, k) {
  happiness.sort((a, b) => b - a);   // largest values first
  let total = 0;
  for (let i = 0; i < k; i++) {      // i = turn index = penalty so far
    const gain = happiness[i] - i;   // value after i decrements
    if (gain <= 0) break;            // rest are 0 too; stop
    total += gain;
  }
  return total;
}

long maximumHappinessSum(int[] happiness, int k) {
    Arrays.sort(happiness);                 // ascending
    long total = 0;
    int n = happiness.length;
    for (int i = 0; i < k; i++) {           // i = turn index = penalty
        long gain = happiness[n - 1 - i] - i; // walk from the largest
        if (gain <= 0) break;               // rest are 0 too; stop
        total += gain;
    }
    return total;
}

long long maximumHappinessSum(vector<int>& happiness, int k) {
    sort(happiness.rbegin(), happiness.rend()); // largest first
    long long total = 0;
    for (int i = 0; i < k; i++) {               // i = turn index = penalty
        long long gain = (long long)happiness[i] - i; // value after i drops
        if (gain <= 0) break;                   // rest are 0 too; stop
        total += gain;
    }
    return total;
}

Explanation

The key observation is that every child still in the queue loses the same amount of happiness over time. After you have made i picks, each remaining child has been decremented exactly i times. So whichever child you pick on turn i, its current value is original − i (floored at 0).

Because the penalty i is identical for every candidate on a given turn, the relative order of the children never changes — the biggest original value is always the biggest current value. That makes the optimal strategy greedy: on each turn pick the largest remaining value. Sorting once in descending order lets us simply walk left to right.

On turn i (0-indexed) we pick happiness[i] and its contribution is happiness[i] − i. Happiness can never go below 0, so if happiness[i] − i ≤ 0 the child contributes nothing — and since the array is sorted, every later pick is also ≤ 0. We can break immediately and return the running total.

Example: happiness = [1, 2, 3], k = 2. Sorted descending → [3, 2, 1]. Turn 0 picks 3 with penalty 0 → +3. Turn 1 picks 2 with penalty 1 → 2 − 1 = +1. Total = 4.

The return type is a 64-bit integer because up to 2·10⁵ values of size 10⁸ can sum past the 32-bit range.

Time: O(n log n) Space: O(1) (in-place sort)