Put Boxes Into the Warehouse I

Problem Statement

In this problem, you are provided with two separate arrays of positive integers. The first array, boxes, contains elements representing the heights of several boxes, while the second array, warehouse, denotes the heights of rooms in a linear warehouse with each room having a unit width. The rooms in the warehouse are sequentially labeled from 0 (leftmost) to n - 1 (rightmost), where n is the length of the warehouse array.

The task is to determine the maximum number of boxes that can be accommodated in the warehouse under specific conditions:

• Boxes cannot be stacked on top of each other.
• The order in which boxes are inserted can be rearranged.
• The insertion process is strictly from left to right.
• A box taller than a room height prevents its placement in that room, and it also blocks the placement of any subsequent boxes.

Ultimately, your goal is to return the maximum number of boxes that can fit into the warehouse adhering to these rules.

Examples

Example 1

Input:

boxes = [4,3,4,1], warehouse = [5,3,3,4,1]

Output:

3

Explanation:

We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
There is no way we can fit all 4 boxes in the warehouse.

Example 2

Input:

boxes = [1,2,2,3,4], warehouse = [3,4,1,2]

Output:

3

Explanation:

Notice that it's not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3.
Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit.
We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead.
Swapping the orange and green boxes is also valid, or swapping one of them with the red box.

Example 3

Input:

boxes = [1,2,3], warehouse = [1,2,3,4]

Output:

1

Explanation:

Since the first room in the warehouse is of height 1, we can only put boxes of height 1.

Constraints

• n == warehouse.length
• 1 <= boxes.length, warehouse.length <= 105
• 1 <= boxes[i], warehouse[i] <= 109

Approach and Intuition

To tackle this problem, consider the following strategy based on sorting and two-pointer techniques, inspired by the given examples and constraints:

1. Sort the Boxes and Adjust Warehouse Limits:

   • First, we sort the box heights in ascending order to try and fit the smallest boxes first which provides more flexibility for fitting the larger boxes subsequently.
   • We also preprocess the warehouse heights to enforce the condition where a box blocked by a shorter room stops the placement of any taller box behind it. This can be done by iterating from the first room to the last and adjusting subsequent room heights to the minimum height encountered so far. This ensures that if a taller box cannot fit in an earlier room, it won't be considered for later rooms that follow the shorter one.

2. Box Placement Using Two Pointers:

   • Set two pointers, one starting at the beginning of the sorted boxes array and the second starting at the start of the adjusted warehouse heights.
   • Iterate through the boxes and attempt to place each one into the warehouse:
     • If the current box fits into the current warehouse room (determined by comparing their heights), place the box and move to the next room and the next box.
     • If the current box does not fit, skip to the next box.
   • Continue this process until all boxes are either placed or deemed unplaceable due to height restrictions.

By following this strategy, we utilize the greedy approach of attempting to place boxes in the smallest available spaces first, which maximizes the potential for placing larger boxes later. Additionally, the preprocessing of the warehouse array ensures that no invalid placements occur, thus streamlining the box placement phase. Remember, the preprocessing of the warehouse is a crucial step as it dynamically adjusts what size of boxes can still be considered as we move through the warehouse.

Solutions

class Solution {
    public int maximumBoxesInStorage(int[] boxes, int[] storageSpaces) {
    
        int idx = boxes.length - 1;
        int boxesCount = 0;
        Arrays.sort(boxes);
    
        for (int space : storageSpaces) {
            while (idx >= 0 && boxes[idx] > space) {
                idx--;
            }
    
            if (idx == -1) return boxesCount;
            boxesCount++;
            idx--;
        }
    
        return boxesCount;
    }
}

class Solution:
    def countBoxes(self, boxes: List[int], rooms: List[int]) -> int:
    
        idx = 0
        tally = 0
        boxes.sort(reverse=True)
    
        for room_height in rooms:
            # Navigate through sorted boxes from largest to smallest
            # Skip boxes that exceed the current room height
            while idx < len(boxes) and boxes[idx] > room_height:
                idx += 1
            if idx == len(boxes):
                return tally
            tally += 1
            idx += 1
    
        return tally