Problem statement

https://leetcode.com/problems/put-boxes-into-the-warehouse-i/

Solution

The idea is to 1) first, process our W, so we alwasy have non-increasing array. 2) sort boxes in decreasing order. 3) start from the smallest box and try to put is as far as possible, if it is OK, put it, if no - take next box and so on.

Complexity

It is O(n + m log m) for time and O(m + n) for space.

Code

class Solution:
    def maxBoxesInWarehouse(self, B, W):
        m, n, ans = len(B), len(W), 0
        
        for i in range(1, n):
            W[i] = min(W[i-1], W[i])
            
        B = sorted(B)[::-1]
        
        i, j = len(W) - 1, len(B) - 1
        while i >= 0 and j >= 0:
            if W[i] >= B[j]:
                ans += 1
                j = j - 1
            i -= 1
                
        return ans