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

Maximum Bags With Full Capacity of Rocks

Number: 2366

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given n bags, each with a maximum capacity and a current number of rocks, determine the maximum number of bags that can be filled to full capacity by optimally distributing a given number of additional rocks.

Key Insights

  • Calculate the additional rocks needed for each bag to be full by subtracting the current rocks from its capacity.
  • Sort these required rocks values in ascending order.
  • Use a greedy approach: iterate over the sorted list and use your available additional rocks to fill bags starting from the smallest requirement.
  • Stop when you run out of rocks for the next bag.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the list of required rocks.
Space Complexity: O(n) for storing the additional rock requirements.

Solution

The problem can be solved by first computing how many additional rocks each bag needs to become full. Then, after sorting these values, use a greedy strategy to distribute the available rocks starting with the bag that requires the fewest rocks. This approach maximizes the count of fully filled bags.

The main data structures used are:

  • An array to store the deficit (additional rocks required) for each bag.
  • Sorting is applied to this array.

The algorithm is straightforward:

  1. Compute the difference (capacity[i] - rocks[i]) for each bag.
  2. Sort the differences.
  3. Iterate through the sorted differences while subtracting each from additionalRocks. Increase the count of fully filled bags until additionalRocks is insufficient for the next bag.

Code Solutions

# Calculate maximum bags that can be filled with full capacity using additional rocks.
def maxBags(capacity, rocks, additionalRocks):
    # Step 1: Calculate how many rocks are needed for each bag to be full.
    needed_rocks = [cap - rock for cap, rock in zip(capacity, rocks)]
    
    # Step 2: Sort the list of additional rocks needed.
    needed_rocks.sort()
    
    full_bags = 0
    
    # Step 3: Distribute additional rocks greedily.
    for needed in needed_rocks:
        # If additionalRocks can cover the needed value, fill the bag.
        if additionalRocks >= needed:
            additionalRocks -= needed
            full_bags += 1
        else:
            # No more rocks can be distributed to fill the next bag.
            break
    return full_bags

# Example usage:
capacity = [2,3,4,5]
rocks = [1,2,4,4]
additionalRocks = 2
print(maxBags(capacity, rocks, additionalRocks))  # Expected output: 3
← Back to All Questions