i (counting from the entrance, starting at 0) has height rooms[i]. You have unit-width boxes with heights boxes.
The rules:
- boxes cannot be stacked, and each room holds at most one box;
- you choose the order in which the boxes go in;
- a box is pushed from left to right; it cannot pass a room lower than itself, and then it and every box behind it stop in front of that room.
Return the largest number of boxes you can fit into the shed.boxes=[2, 5, 3, 1], rooms=[6, 4, 4, 2] → 4
Push box 1 all the way to room 3, box 3 into room 2, box 2 into room 1, and box 5 stays in room 0 at the entrance. All four fit.
boxes=[4, 4, 1], rooms=[3, 5, 5] → 1
The entrance room is only 3 high, so neither box of height 4 gets past it; only box 1 fits.
boxes=[2, 2, 2], rooms=[9, 1, 9] → 1
A box of height 2 cannot pass room 1, so nothing can go beyond it. One box fits, in room 0.
boxes=[2, 5, 3, 1], rooms=[6, 4, 4, 2]
4
Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.