DEV Community

Cover image for 3075. Maximize Happiness of Selected Children
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

1

3075. Maximize Happiness of Selected Children

3075. Maximize Happiness of Selected Children

Medium

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

Solution:

class Solution {

    /**
     * @param Integer[] $happiness
     * @param Integer $k
     * @return Integer
     */
    function maximumHappinessSum($happiness, $k) {
        $ans = 0;
        $decremented = 0;

        sort($happiness);
        rsort($happiness);

        for ($i = 0; $i < $k; ++$i) {
            $ans += max(0, $happiness[$i] - $decremented);
            ++$decremented;
        }

        return $ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay