CraftHaven Records keeps one long row of m fixed shelf-slots along a back wall; slot i can hold a crate whose required clearance is at most slots[i]. Across a shift, n archive crates arrive one at a time, in a fixed order, and crate k requires a slot whose clearance is at least crates[k]. When crate k arrives, the clerk scans the shelf-slots from left (index 0) to right and places the crate into the first slot that is (1) still empty and (2) has clearance >= crates[k]. Once a slot receives a crate it stays occupied forever -- it can never be reused for a later crate. If crate k finds no eligible empty slot anywhere in the row, it is left on the loading cart (unplaced) and the clerk moves on to the next crate. After every crate has been processed in order, report how many of the n crates ended up unplaced.
n and m -- the number of crates and the number of shelf-slots.n integers crates[0..n-1] -- the required clearance of each crate, listed in arrival order.m integers slots[0..m-1] -- the clearance of each shelf-slot, listed left to right.A single integer: the number of crates that remain unplaced after all crates have been processed.
Example 1
Input
3 2 4 2 5 3 6
Expected
1
Explanation
Crate0 needs clearance>=4: slot0=3 is too small, slot1=6 qualifies, so crate0 takes slot1. Crate1 needs>=2: slot0=3 qualifies (slot1 is taken), so crate1 takes slot0. Crate2 needs>=5: both slots are now occupied, so crate2 is unplaced. Answer: 1.
Example 2
Input
4 3 1 1 1 1 1 1 1
Expected
1
Explanation
Crates 0,1,2 each need clearance>=1 and take slots 0,1,2 in order (each slot exactly meets the requirement). Crate3 also needs>=1 but every slot is already occupied, so it is unplaced. Answer: 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →