i (left to right, 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;
- each box may be pushed in from either end; 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, 1, 4, 2] → 3
Box 5 goes in from the left into room 0. From the right, box 2 goes into room 3 and box 3 into room 2. Box 1 has nowhere left: room 1 can only be reached through occupied rooms. Three in total.
boxes=[3, 3, 3], rooms=[2, 7, 2] → 0
Both entrances are only 2 high, so a box of height 3 cannot get in from either side.
boxes=[1, 1, 1], rooms=[3, 1, 3] → 3
Boxes of height 1 pass everywhere, so all three rooms get filled.
boxes=[2, 5, 3, 1], rooms=[6, 1, 4, 2]
3
Run checks the first 3 tests in your browser. Submit checks all 139 tests on the server, hidden ones included.