Fruits Into Baskets III
Real-world version: Crates Into Rated Shelf SlotsThe statement here is our own: the same inputs, outputs and technique.
A depot has a row of shelf slots, left to right, and baskets[j] is the load rating of slot j in kilograms. Crates arrive one at a time in the order given by fruits, and fruits[i] is the weight of the i-th crate.
Each arriving crate is handled by the same rule: scan the slots from left to right and put the crate in the first still-empty slot whose rating is greater than or equal to the crate's weight. A slot holds at most one crate, and once a crate is in a slot it is never moved. If no still-empty slot is rated high enough, that crate is turned away and the slots are left as they were before it arrived.
Return how many crates end up turned away.
Examples
Example 1
- Input
- fruits = [4,2,5], baskets = [3,5,4]
- Output
- 1
The 4 kg crate skips slot 0, rated 3, and lands in slot 1, rated 5. The 2 kg crate then takes slot 0, which is still empty and rated high enough. The 5 kg crate finds only slot 2 free, rated 4, so it is turned away.
Example 2
- Input
- fruits = [6,6,1], baskets = [6,2,9]
- Output
- 0
The first 6 kg crate takes slot 0, whose rating of 6 exactly matches it. The second 6 kg crate passes slot 1, rated 2, and takes slot 2. The 1 kg crate takes slot 1, so no crate is turned away.
Example 3
- Input
- fruits = [2,2,2], baskets = [9,1,1]
- Output
- 2
The first 2 kg crate takes slot 0. Slots 1 and 2 are both rated 1, below 2 kg, so the other two crates are turned away.
Constraints
- n == fruits.length
- n == baskets.length
- fruits.length == baskets.length
- 1 <= fruits.length <= 10^5
- 1 <= baskets.length <= 10^5
- 1 <= fruits[i] <= 10^9
- 1 <= baskets[i] <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def num_of_unplaced_fruits(fruits: list[int], baskets: list[int]) -> int:public int numOfUnplacedFruits(int[] fruits, int[] baskets)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's