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

Put Boxes Into the Warehouse I

Number: 1703

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

We are given two arrays: one representing the heights of various boxes and the other representing the heights of rooms in a warehouse laid out from left to right. Boxes are inserted into the warehouse from left to right and cannot be stacked. A box can be inserted into a room if its height is less than or equal to the room's available height. However, each room is affected by the maximum height of the preceding rooms. The goal is to find the maximum number of boxes that can be successfully placed into the warehouse by appropriately reordering the boxes.

Key Insights

  • Preprocess the warehouse heights by updating each room’s height to the minimum height encountered so far (from left to right) so that each room’s effective capacity is captured.
  • Sort the boxes in descending order so that the largest boxes, which need higher clearance, are considered first.
  • Traverse the warehouse from rightmost room to leftmost room, and for each room, if the current largest box fits, place it.
  • The greedy approach ensures that we optimize the placement of boxes by using each room’s capacity efficiently.

Space and Time Complexity

Time Complexity: O(m log m + n) where m is the number of boxes and n is the number of warehouse rooms. Space Complexity: O(n) for storing the modified warehouse effective heights (in-place modification is possible).

Solution

The solution involves two main steps: first, modify the warehouse array such that each element represents the maximum allowable box height for that room. This is achieved by taking the cumulative minimum of the warehouse heights from left to right. Second, sort the boxes in descending order and starting from the rightmost warehouse room, try to place the largest available box that can fit. If it fits, move to the next box; otherwise, check the next room. This greedy approach ensures we maximize the number of boxes placed.

Code Solutions

# Python solution

def maxBoxesInWarehouse(boxes, warehouse):
    # Preprocess the warehouse: update each room's capacity to the minimum seen so far
    n = len(warehouse)
    for i in range(1, n):
        warehouse[i] = min(warehouse[i], warehouse[i - 1])
    
    # Sort boxes in descending order to place larger boxes first
    boxes.sort(reverse=True)
    
    count = 0   # Count for placed boxes
    j = 0       # Pointer for the current box in the sorted boxes list
    
    # Iterate over the warehouse from the last room to the first room
    for i in range(n - 1, -1, -1):
        # If there are boxes left and the current box can fit in the room
        if j < len(boxes) and boxes[j] <= warehouse[i]:
            count += 1  # Place the box in this room
            j += 1      # Move to the next box
    return count

# Example usage:
# boxes = [4, 3, 4, 1]
# warehouse = [5, 3, 3, 4, 1]
# print(maxBoxesInWarehouse(boxes, warehouse))  # Output: 3
← Back to All Questions