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:
![](https://spcdn.pages.dev/leetcode/problems/1580.Put%20Boxes%20Into%20the%20Warehouse%20II/images/22.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/1580.Put%20Boxes%20Into%20the%20Warehouse%20II/images/22-2.png)
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#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 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
}
|