Fruits Into Baskets III
You receive two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the i th type of fruit, and baskets[j] represents the capacity of the j th basket.
From left to right, place the fruits according to these rules:
-
Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
-
Each basket can hold only one type of fruit.
-
If a fruit type cannot be placed in any basket, it remains unplaced.
Produce the number of fruit types that remain unplaced after all possible allocations are made.
Input: fruits = [4,2,5], baskets = [3,5,4]
Output: 1
Explanation:
-
fruits[0] = 4is placed inbaskets[1] = 5. -
fruits[1] = 2is placed inbaskets[0] = 3. -
fruits[2] = 5cannot be placed inbaskets[2] = 4.
Since one fruit type remains unplaced, we produce 1.
Input: fruits = [3,6,1], baskets = [6,4,7]
Output: 0
Explanation:
-
fruits[0] = 3is placed inbaskets[0] = 6. -
fruits[1] = 6cannot be placed inbaskets[1] = 4(insufficient capacity) but can be placed in the next available basket,baskets[2] = 7. -
fruits[2] = 1is placed inbaskets[1] = 4.
Since all fruits are successfully placed, we produce 0.
Constraints
n == fruits.length == baskets.length1 <= n <= 10^51 <= fruits[i], baskets[i] <= 10^9
Did this problem appear in one of your interviews?
Responses stay private.