Place Fruit Types in the Leftmost Eligible Baskets
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given two integer arrays, `fruits` and `baskets`, each of length `n`. The value `fruits[i]` is the quantity of fruit type `i`, and `baskets[j]` is basket `j`'s capacity.
Process fruit types in their original order, from left to right. For each type:
- Place its entire quantity in the leftmost unused basket whose capacity is at least that quantity.
- A basket can be assigned only one fruit type, even if some capacity would remain.
- If no unused basket has enough capacity, leave that fruit type unplaced and continue to the next type.
Return the number of fruit types left unplaced after this process.
### C++ Interface
```cpp
class Solution {
public:
int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
}
};
```
### Examples
**Example 1**
```text
Input: fruits = [2,6,4], baskets = [6,3,4]
Output: 1
```
The quantity `2` must use basket `0`, since it is the leftmost eligible basket. The quantity `6` then has no eligible unused basket and remains unplaced. The quantity `4` uses basket `2`. The answer is `1`; assigning the first fruit to a different basket would violate the required process.
**Example 2**
```text
Input: fruits = [5,5,1,6], baskets = [5,1,5,6]
Output: 0
```
The fruit types use basket indices `0`, `2`, `1`, and `3`, respectively. Equal capacity is sufficient, and an earlier basket skipped for one type can still hold a later, smaller type. Every type is placed.
### Constraints
- `n == fruits.length == baskets.length`.
- `1 <= n <= 100000`.
- `1 <= fruits[i], baskets[i] <= 1000000000`.
### Clarifying Questions
- Is the goal to choose an allocation with as few unplaced types as possible? No. The fruit order and leftmost-basket rule determine the process.
- Does “leftmost” refer to the smallest capacity? No. It refers to the smallest original basket index among unused baskets with enough capacity.
- Can one fruit type be split across baskets, or can a basket be reused for another type? Neither is allowed.
### What a Strong Answer Covers
- The original processing order and exact leftmost-eligible rule.
- Basket availability after a successful placement and after a failed placement.
- Equal capacities, repeated quantities, and a single basket.
- A correctness argument and resource bounds for `100000` fruit types.
### Follow-up Questions
- Can the required process leave a type unplaced even though another allocation would place every type?
- What changes if a used basket can later be released before processing the next fruit type?
```hint Preserve basket positions
A segment tree over original basket indices can store the largest unused capacity in each range. If a range can hold the current quantity, inspect its left child first to find the leftmost eligible basket.
```
Overview: Process fruit types in order and use the leftmost unused basket with enough capacity for each whole quantity. Count unplaced types while preserving original basket positions and one-use availability.