Fruits Into Baskets III

Problem Description

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth 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.

Return the number of fruit types that remain unplaced after all possible allocations are made.

Key Insights

• Each fruit type needs to be placed in the leftmost basket that can accommodate its quantity.
• Baskets can only hold one type of fruit, which means once a basket is filled, it cannot be reused.
• The solution requires efficiently finding the first available basket for each fruit type.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the baskets. Space Complexity: O(n) - for storing basket capacities if necessary.

Solution

To solve the problem, we can follow these steps:

1. Sort the baskets array to easily find the smallest available basket that can hold the fruit.
2. Use a two-pointer approach to iterate through the fruits and baskets arrays.
3. For each fruit, check if it can be placed in the available baskets, starting from the leftmost.
4. If a fruit type cannot be placed in any basket, count it as unplaced.

This approach ensures that we effectively utilize the available baskets and count the unplaced fruits.

Code Solutions