# 1580. Put Boxes Into the Warehouse II

## Description

You are given two arrays of positive integers, boxes and warehouse, representing the heights of some boxes of unit width and the heights of n rooms in a warehouse respectively. The warehouse's rooms are labeled from 0 to n - 1 from left to right where warehouse[i] (0-indexed) is the height of the ith room.

Boxes are put into the warehouse by the following rules:

• Boxes cannot be stacked.
• You can rearrange the insertion order of the boxes.
• Boxes can be pushed into the warehouse from either side (left or right)
• If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.

Return the maximum number of boxes you can put into the warehouse.

Example 1:

Input: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
Output: 4
Explanation:

We can store the boxes in the following order:
1- Put the yellow box in room 2 from either the left or right side.
2- Put the orange box in room 3 from the right side.
3- Put the green box in room 1 from the left side.
4- Put the red box in room 0 from the left side.
Notice that there are other valid ways to put 4 boxes such as swapping the red and green boxes or the red and orange boxes.


Example 2:

Input: boxes = [3,5,5,2], warehouse = [2,1,3,4,5]
Output: 3
Explanation:

It is not possible to put the two boxes of height 5 in the warehouse since there's only 1 room of height >= 5.
Other valid solutions are to put the green box in room 2 or to put the orange box first in room 2 before putting the green and red boxes.


Constraints:

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

## Solutions

• class Solution {
public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
int n = warehouse.length;
int[] left = new int[n];
int[] right = new int[n];
final int inf = 1 << 30;
left[0] = inf;
right[n - 1] = inf;
for (int i = 1; i < n; ++i) {
left[i] = Math.min(left[i - 1], warehouse[i - 1]);
}
for (int i = n - 2; i >= 0; --i) {
right[i] = Math.min(right[i + 1], warehouse[i + 1]);
}
for (int i = 0; i < n; ++i) {
warehouse[i] = Math.min(warehouse[i], Math.max(left[i], right[i]));
}
Arrays.sort(boxes);
Arrays.sort(warehouse);
int ans = 0, i = 0;
for (int x : boxes) {
while (i < n && warehouse[i] < x) {
++i;
}
if (i == n) {
break;
}
++ans;
++i;
}
return ans;
}
}

• class Solution {
public:
int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
int n = warehouse.size();
const int inf = 1 << 30;
vector<int> left(n, inf);
vector<int> right(n, inf);
for (int i = 1; i < n; ++i) {
left[i] = min(left[i - 1], warehouse[i - 1]);
}
for (int i = n - 2; ~i; --i) {
right[i] = min(right[i + 1], warehouse[i + 1]);
}
for (int i = 0; i < n; ++i) {
warehouse[i] = min(warehouse[i], max(left[i], right[i]));
}
sort(boxes.begin(), boxes.end());
sort(warehouse.begin(), warehouse.end());
int ans = 0;
int i = 0;
for (int x : boxes) {
while (i < n && warehouse[i] < x) {
++i;
}
if (i == n) {
break;
}
++ans;
++i;
}
return ans;
}
};

• class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
n = len(warehouse)
left = [0] * n
right = [0] * n
left[0] = right[-1] = inf
for i in range(1, n):
left[i] = min(left[i - 1], warehouse[i - 1])
for i in range(n - 2, -1, -1):
right[i] = min(right[i + 1], warehouse[i + 1])
for i in range(n):
warehouse[i] = min(warehouse[i], max(left[i], right[i]))
boxes.sort()
warehouse.sort()
ans = i = 0
for x in boxes:
while i < n and warehouse[i] < x:
i += 1
if i == n:
break
ans, i = ans + 1, i + 1
return ans


• func maxBoxesInWarehouse(boxes []int, warehouse []int) (ans int) {
n := len(warehouse)
left := make([]int, n)
right := make([]int, n)
const inf = 1 << 30
left[0] = inf
right[n-1] = inf
for i := 1; i < n; i++ {
left[i] = min(left[i-1], warehouse[i-1])
}
for i := n - 2; i >= 0; i-- {
right[i] = min(right[i+1], warehouse[i+1])
}
for i := 0; i < n; i++ {
warehouse[i] = min(warehouse[i], max(left[i], right[i]))
}
sort.Ints(boxes)
sort.Ints(warehouse)
i := 0
for _, x := range boxes {
for i < n && warehouse[i] < x {
i++
}
if i == n {
break
}
ans++
i++
}
return
}