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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Total Beauty of the Gardens

Difficulty: Hard

Problem Description

Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens. You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the i-th garden. You are also given another integer newFlowers, which is the maximum number of flowers that Alice can additionally plant. The beauty of the gardens can be calculated based on the number of complete and incomplete gardens. Return the maximum total beauty that Alice can obtain after planting at most newFlowers flowers.

Key Insights

  • A garden is considered complete if it has at least target flowers.
  • The total beauty is the sum of complete gardens multiplied by full, and the minimum number of flowers in incomplete gardens multiplied by partial.
  • The goal is to efficiently distribute newFlowers to maximize the total beauty.
  • We can utilize greedy algorithms, binary search, and prefix sums to find the optimal distribution of flowers.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve the problem, we can follow these steps:

  1. Sort the flowers array: This allows us to efficiently determine how many flowers are needed to make each garden complete or the minimum number of flowers in incomplete gardens.
  2. Binary Search for Maximum Minimum: Use binary search to determine the maximum possible minimum number of flowers in incomplete gardens after distributing the newFlowers.
  3. Greedy Distribution: For each potential minimum flower count (from binary search), calculate how many flowers are required to achieve that count for incomplete gardens and check if those flowers can be accommodated within newFlowers.
  4. Calculate Total Beauty: Based on the number of complete gardens and the calculated minimum flowers in incomplete gardens, compute the total beauty and track the maximum found.

Code Solutions

def maxBeauty(flowers, newFlowers, target, full, partial):
    flowers.sort()
    n = len(flowers)

    def canAchieve(minIncomplete):
        required = 0
        complete = 0

        for f in flowers:
            if f >= target:
                complete += 1
            elif f + newFlowers < minIncomplete:
                required += minIncomplete - f
        
        return required <= newFlowers, complete

    left, right = 0, target
    max_beauty = 0

    while left <= right:
        mid = (left + right) // 2
        required, complete = canAchieve(mid)

        if required:
            max_beauty = max(max_beauty, complete * full + mid * partial)
            left = mid + 1
        else:
            right = mid - 1

    return max_beauty
← Back to All Questions