LeetCode 1564: Put Boxes Into the Warehouse I

Explanation

Given the heights of the boxes and the heights of the warehouse shelves, the task is to find the maximum number of boxes that can be put into the warehouse from left to right while respecting the height constraints.

To solve this problem, we can sort the heights of the boxes and the heights of the shelves in non-increasing order. Then, we can iterate from left to right and try to place each box in the warehouse at the lowest possible shelf height that can accommodate it. We can use two pointers to keep track of the current box and the current shelf being considered.

Algorithm:

1. Sort the box heights and shelf heights in non-increasing order.
2. Initialize two pointers, one for the current box and one for the current shelf.
3. Iterate through the boxes:
   • If the current box height is less than or equal to the current shelf height, increment the count of boxes placed and move to the next box and the next shelf.
   • If the current box height is greater than the current shelf height, move to the next shelf.
4. Return the count of boxes placed.

Time complexity: O(nlogn) where n is the number of boxes or shelves. Space complexity: O(1) as we are using constant extra space.

class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        Arrays.sort(boxes);
        Arrays.sort(warehouse);

        int count = 0;
        int boxIdx = 0;
        int shelfIdx = warehouse.length - 1;

        while (boxIdx < boxes.length && shelfIdx >= 0) {
            if (boxes[boxIdx] <= warehouse[shelfIdx]) {
                count++;
                boxIdx++;
            }
            shelfIdx--;
        }

        return count;
    }
}