# 1564. Put Boxes Into the Warehouse I

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fb3wUGcWPnPARUy7G7lus%2F%E5%9C%96%E7%89%87.png?alt=media\&token=c7a47bc4-d883-4ba7-be25-d19cbb506bb4)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F7PwTGrouoRwgib5xqHgt%2F%E5%9C%96%E7%89%87.png?alt=media\&token=fa0b8949-b977-4951-8135-daee237f3f9d)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FLF5ntxeaTux32x6rTmXX%2F%E5%9C%96%E7%89%87.png?alt=media\&token=0875f4f8-4724-459b-b82f-f0f55afcef3a)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FLaQBLgEG9dkftH40spsd%2F%E5%9C%96%E7%89%87.png?alt=media\&token=1232a8b3-83c3-478c-920d-e3188eff7e9e)

## 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)
```

```java
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)
```

```java
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)
```

```java
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;
    }
}
```