Problem Statement in English

You’re given a 0-indexed integer array happiness of length n, where happiness[i] represents the happiness value of the i-th child.

You are also given an integer k, which represents the number of children you can select.

Your task is to select exactly k children such that the total happiness is maximized. The happiness of a selected child decreases by 1 for each subsequent child selected after them.

The happiness value of a child cannot be negative; if the calculated happiness is less than 0, it is considered to be 0.

Return the maximum total happiness you can achieve by selecting exactly k children.

Approach

To solve the problem of maximizing the total happiness of selected children, we can use a greedy approach.

The key idea is to prioritize selecting children with the highest happiness values first, as their contributions will be reduced less by the subsequent selections.

After that we just need to keep track of the current time so that we can subtract it from the happiness value of the child being selected.

Solution in Python


class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        time = res = ptr = 0

        while k and ptr < len(happiness):
            h = happiness[ptr] - time
            h = max(h, 0)

            res += h

            k -= 1
            time += 1
            ptr += 1

        return res

Complexity

  • Time: $O(n \log n)$
    Since we need to sort the happiness array.

  • Space: $O(1)$
    Since we are using only constant space.

And we are done.