The Question
Coding

First Fit Fruit Placement

Given an array 'fruits' representing the size of fruits and an array 'baskets' representing the capacity of baskets, simulate the following process: for each fruit in the order they appear, place it in the first available basket (lowest index) that has a capacity greater than or equal to the fruit's size. Once a fruit is placed, that basket is no longer available. Return the total number of fruits that could not be placed in any basket. Optimize the solution to handle arrays of size up to 10^5.
Java
Segment Tree
Range Maximum Query
Binary Search on Tree
Questions & Insights

Clarifying Questions

What are the constraints on $N$ (the number of fruits and baskets)? (Assuming N \le 10^5, which implies an O(n^2) solution will be too slow and an O(n \log n) approach is required).
Can a basket hold more than one fruit? (Assuming each basket can hold exactly one fruit, and once used, it is no longer available).
Is the order of fruits fixed? (Assuming we must process fruits in the given order from index 0 to n-1).
What is the definition of "first available"? (Assuming we search baskets from index 0 to n-1 and pick the smallest index j such that baskets[j] >= fruits[i]).

Thinking Process

To find the first index j in baskets that satisfies baskets[j] >= fruits[i], a linear search would take O(N) per fruit, leading to O(N^2) total time. We need a more efficient way to query for values and update "used" baskets.
We can use a Segment Tree where each node stores the maximum capacity in its respective range. This allows us to determine if a valid basket exists in the left sub-tree or the right sub-tree in O(1) at each node level.
For each fruit:
Perform a "Tree Walk" on the Segment Tree to find the leftmost index j where the value is \ge the fruit size.
If an index j is found, update the value at that index in the Segment Tree to -1 (effectively marking it as exhausted/removed) and decrement the capacity.
If no index is found, the fruit remains unplaced.
The total complexity will be O(N \log N), which fits within the time limits for N = 10^5.
Implementation Breakdown

Problem Set

Input: Two integer arrays fruits and baskets of length n.
Output: The number of fruits that could not be placed in any basket.
Constraints: 1 \le n \le 10^5, 1 \le fruits[i], baskets[i] \le 10^9.

Approach

Algorithm: Segment Tree (Range Maximum Query + Point Update).
Data Structure: Array-based Segment Tree.
Complexity:
Time: O(N \log N) to build the tree and perform N searches and updates.
Space: O(N) to store the segment tree nodes.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: While the Segment Tree is O(N \log N), for small N (e.g., N < 1000), a simple O(N^2) linear search is faster due to lower constant factors and cache locality.
Alternative Data Structures: A Fenwick Tree (Binary Indexed Tree) is usually harder to use for "find first element \ge X" queries because it is optimized for prefix sums. However, a Square Root Decomposition could achieve O(N \sqrt{N}), which might pass if constraints are lenient.
Parallelization: Building the Segment Tree can be parallelized, but the fruit placement process is inherently sequential because each placement affects the availability of baskets for subsequent fruits.