1580. Put Boxes Into the Warehouse II

https://leetcode.com/problems/put-boxes-into-the-warehouse-ii/

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

from left, cal the min height

height = [3,3,1,1]

from right, cal max height with min

height = [3,3,1,2]

sort height: [1,2, 3,3]

sort box: [1,2,2,3,4]

put box into height one by one if matches, count++

T:O(nlogn + 2*n + mlogm + n), n - warehouse, m - box..
S: O(n)

from left, cal the min height
height = [3,3,1,1]

from right, cal max height with min
height = [3,3,1,2]

[1, 2, 3, 3] height
[1, 2, 2, 3, 4] box

因為是從高度小的開始放, 放到也是高度小的 warehouse, 所以是ok的

origi:3412
after:3312

所以以這個例子來說, 從小的高開始放這樣就會慢慢發散出去左右放, 小的先入, 所以也不會有塞車的問題

left   小  right 
  3  3  1  2

class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        int n = warehouse.length;
        int height[] = new int[n];
        
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, warehouse[i]);
            height[i] = min;
        } // 3311
        
        min = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            min = Math.min(min, warehouse[i]);
            height[i] = Math.max(height[i], min);
        } // 3312

        Arrays.sort(height);
        Arrays.sort(boxes);
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (count < boxes.length && boxes[count] <= height[i]) {
                count++;
            }
        }
        return count;
    }
}

greedy

like 1564 leetcode solution 2:

sort box desc, put into it, left can put or put into right

T:O(mlogm + m), m - box..
S: O(1)

class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        Arrays.sort(boxes);
        
        int left = 0;
        int right = warehouse.length - 1;
        int count = 0;
        for (int i = boxes.length - 1; i >= 0; i--) { // box in desc
            if (left <= right) {
                if (boxes[i] <= warehouse[left]) { // put in left side
                    count++;
                    left++;
                } else if (boxes[i] <= warehouse[right]) { // put in right side
                    count++;
                    right--;
                }
            }
        }
        return count;
    }
}