Question

3075. Maximize Happiness of Selected Children

中文文档

Description

You are given an array happiness of length n, and a positive integer k.

There are n children standing in a queue, where the ith child has happiness value happiness[i]. You want to select k children from these n children in k turns.

In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.

Return _the maximum sum of the happiness values of the selected children you can achieve by selecting _k _children_.

 

Example 1:

Input: happiness = [1,2,3], k = 2
Output: 4
Explanation: We can pick 2 children in the following way:
- Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
- Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0.
The sum of the happiness values of the selected children is 3 + 1 = 4.

Example 2:

Input: happiness = [1,1,1,1], k = 2
Output: 1
Explanation: We can pick 2 children in the following way:
- Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
- Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
The sum of the happiness values of the selected children is 1 + 0 = 1.

Example 3:

Input: happiness = [2,3,4,5], k = 1
Output: 5
Explanation: We can pick 1 child in the following way:
- Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
The sum of the happiness values of the selected children is 5.

 

Constraints:

• 1 <= n == happiness.length <= 2 * 105
• 1 <= happiness[i] <= 108
• 1 <= k <= n

Solutions

Solution 1: Greedy + Sorting

To maximize the sum of happiness, we should prioritize choosing children with higher happiness values. Therefore, we can sort the children in descending order of happiness, and then select $k$ children in sequence. For the current $i$-th child, the happiness value that can be obtained is $\max(happiness[i] - i, 0)$. Finally, we return the sum of the happiness values of these $k$ children.

The time complexity is $O(n \times \log n + k)$ and the space complexity is $O(\log n)$, where $n$ is the length of the happiness array.

class Solution:
  def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
    happiness.sort(reverse=True)
    ans = 0
    for i, x in enumerate(happiness[:k]):
      x -= i
      ans += max(x, 0)
    return ans

class Solution {
  public long maximumHappinessSum(int[] happiness, int k) {
    Arrays.sort(happiness);
    long ans = 0;
    for (int i = 0, n = happiness.length; i < k; ++i) {
      int x = happiness[n - i - 1] - i;
      ans += Math.max(x, 0);
    }
    return ans;
  }
}

class Solution {
public:
  long long maximumHappinessSum(vector<int>& happiness, int k) {
    sort(happiness.rbegin(), happiness.rend());
    long long ans = 0;
    for (int i = 0, n = happiness.size(); i < k; ++i) {
      int x = happiness[i] - i;
      ans += max(x, 0);
    }
    return ans;
  }
};

func maximumHappinessSum(happiness []int, k int) (ans int64) {
  sort.Ints(happiness)
  for i := 0; i < k; i++ {
    x := happiness[len(happiness)-i-1] - i
    ans += int64(max(x, 0))
  }
  return
}

function maximumHappinessSum(happiness: number[], k: number): number {
  happiness.sort((a, b) => b - a);
  let ans = 0;
  for (let i = 0; i < k; ++i) {
    const x = happiness[i] - i;
    ans += Math.max(x, 0);
  }
  return ans;
}