Maximize Happiness of Selected Children — Algorithm Visualization & Coding Challenge

😊 Maximize Happiness of Selected Children

Difficulty: Medium
Topics: Greedy, Sorting

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

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

🔁 Selection Rules

• In each turn, when you select a child:
  • The happiness value of all unselected children decreases by 1
  • Happiness values cannot become negative
  • Decrement happens only if the value is positive

🎯 Goal

Return the maximum possible sum of happiness values of the selected children after selecting exactly k children.

🧠 Example 1

Input:

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

Output:

4

Explanation:

• Pick the child with happiness 3
  • Remaining happiness becomes [0, 1]
• Pick the child with happiness 1
  • Remaining happiness becomes [0]

Total happiness = 3 + 1 = 4

🧠 Example 2

Input:

happiness = [1, 1, 1, 1]
k = 2

Output:

1

Explanation:

• Pick any child with happiness 1
  • Remaining happiness becomes [0, 0, 0]
• Pick a child with happiness 0

Total happiness = 1 + 0 = 1

🧠 Example 3

Input:

happiness = [2, 3, 4, 5]
k = 1

Output:

5

Explanation:

• Pick the child with happiness 5
  • Remaining happiness becomes [1, 2, 3]

Total happiness = 5

📐 Constraints

• 1 ≤ n == happiness.length ≤ 2 × 10⁵
• 1 ≤ happiness[i] ≤ 10⁸
• 1 ≤ k ≤ n