Amazon OA: Minimum Boxes to Unload
The supply chain manager at one of Amazon’s warehouses is shipping the last container of the day. All n boxes have been loaded into the truck, with their sizes represented in the array boxes.
The truck may not have enough capacity to store all the boxes, so some of the boxes may have to be unloaded. The remaining boxes must satisfy the condition:
max(boxes) <= capacity * min(boxes)Given the array boxes and capacity, find the minimum number of boxes that need to be unloaded.
Example
Given n = 4, boxes = [1, 4, 3, 2], and capacity = 2.
Unloading box 0 with size 1 leaves [4, 3, 2].
Now max([4, 3, 2]) = 4 and capacity * min([4, 3, 2]) = 2 * 2 = 4.
This satisfies the required condition, so the answer is 1.
Function Description
Complete the function removeBoxes in the editor below.
public static int removeBoxes(List<Integer> boxes, int capacity)Returns
An integer denoting the minimum number of boxes that need to be unloaded.
Sample Input For Custom Testing
6
4
5
3
8
3
7
2Sample Output
2Explanation
Remove boxes of size 8 and 7. Then the remaining boxes are [4, 5, 3, 3], where max = 5 and min = 3, and 5 <= 3 * 2.
Alternatively, remove the two boxes of size 3. Then the remaining boxes are [4, 5, 8, 7], where max = 8 and min = 4, and 8 <= 4 * 2.
这道题的核心是：删除尽量少的箱子，使剩余箱子满足“最大值 ≤ capacity × 最小值”。把数组排序后，问题就转化成找一个最长的连续区间，使区间内最大值和最小值之比不超过 capacity。由于排序后区间最小值和最大值分别落在两端，可以用双指针 / 滑动窗口从左到右维护窗口右端，检查当前最小值对应的最大可扩展右端，计算需要删除的元素数并取最小值。整体思路简单高效，通常可做到 O(n log n)（排序）加 O(n) 扫描，非常适合 OA 面试题。
