We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Happiness of Selected Children

Number: 3351

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

You are given an array of positive integers representing the happiness values of n children standing in a queue and a positive integer k. In k turns, you select one child per turn. When a child is selected, the happiness value of every child who is not yet selected decreases by 1 (if it is positive). Your goal is to maximize the total sum of the happiness values of the selected children.

Key Insights

  • The order of selection matters: earlier selections avoid more decrements.
  • When a child is selected at turn r, its effective contribution is max(happiness - (r - 1), 0).
  • To maximize the contribution, assign early turns to the children with the highest happiness values.
  • Sorting the array in descending order and then selecting the first k children (with each child’s effective happiness reduced by its turn index) yields the optimal solution.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the sorted array (or O(1) if sorting in-place).

Solution

We start by sorting the given array in descending order so that the child with the highest happiness comes first. For each of the first k children in the sorted list, compute its contribution by subtracting its turn index (starting from 0) from its initial happiness, ensuring the value does not drop below 0. Summing these contributions gives the maximum total happiness. The greedy approach works because high-value children lose less additional value when chosen earlier.

Code Solutions

# Define the function that maximizes the sum of selected children's happiness values
def maximize_happiness(happiness, k):
    # Sort the happiness array in descending order
    sorted_happiness = sorted(happiness, reverse=True)
    total_happiness = 0
    # Iterate over the first k children and compute their effective happiness
    for i in range(k):
        # Calculate effective happiness after decrements from previous selections
        effective_happiness = max(sorted_happiness[i] - i, 0)
        total_happiness += effective_happiness
    return total_happiness

# Example usage:
if __name__ == "__main__":
    print(maximize_happiness([1,2,3], 2))  # Expected output: 4
← Back to All Questions