1564. Put Boxes Into the Warehouse I

naive

sort boxes, then put them one by one into warehouse,

T: (mlogm + n^2), m is number of boxes, n is number of warehouses

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

put w[3], make sure box <= w[0~2]
put w[2], make sure box <= w[0~1]
put w[1], make sure box <= w[0]

for (i = w.length -1; ) {
	for (j = i - 1; j >= 0 ; j--) {
	   if (
	}
}

DP

[1,3,4,4]  
 i i i 
 
[5,3,3,4,1]
 5 3 3 3 1
 4     3 1
 
dp[i] min warehouse's height for box height

dp[0] = w[0];
dp[1] = Math.min(dp[0], w[1])

dp[i] = Math.min(dp[i-1], w[i])


T: O(n + mlogm + n), m is number of boxes, n is number of warehouse
S: O(n)

class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        int n = warehouse.length;
        int dp[] = new int[n];
        dp[0] = warehouse[0];
        
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[i-1], warehouse[i]);
        }
        Arrays.sort(boxes);
        
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (count < boxes.length && boxes[count] <= dp[i]) {
                count++; // after set to warehouse, boxIdx++
            }
        }
        return count;
    }
}j

but can be more simple

greedy

like greedy idea, use warehouse itself

T: O(n + mlogm + n), m is number of boxes, n is number of warehouse
S: O(1)

class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        int n = warehouse.length;
        for (int i = 1; i < n; i++) {
            warehouse[i] = Math.min(warehouse[i-1], warehouse[i]);
        }
        Arrays.sort(boxes);
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (count < boxes.length && boxes[count] <= warehouse[i]) {
                count++;
            }
        }
        return count;
    }
}

but if interview ask, you can't use in-place, how to achive space O(1)

sort boxes, from large to small, set to warehouse, then it'll abandon box which is too tall !

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

T: O(mlogm + m), m is number of boxes
S: O(1)

class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        Arrays.sort(boxes);
        
        int count = 0;
        for (int i = boxes.length - 1; i >= 0; i--) {
            if (count < warehouse.length && boxes[i] <= warehouse[count]) {
                count++;
            }
        }
        return count;
    }
}