Place items into earliest fitting bins

You are given k items with sizes items[0..k-1] and n bins with initial capacities caps[0..n-1]. Process items in order; for each size x, place it into the leftmost bin whose remaining capacity is at least x, then reduce that bin’s remaining capacity by x. If no such bin exists, the item remains unplaced. Return the number of unplaced items. Design an algorithm that supports up to 2×10^5 items and bins in total with O((n + k) log n) time, describing the data structure you would use.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Place items into earliest fitting bins

You are given k items with sizes items[0..k-1] and n bins with initial capacities caps[0..n-1]. Process the items in order. For each size x, place it into the leftmost bin whose remaining capacity is at least x, then reduce that bin's remaining capacity by x. If no such bin exists, the item remains unplaced. Return the number of unplaced items.

Design an algorithm that supports up to 2*10^5 items and bins in total in O((n + k) log n) time. A max segment tree over bin capacities lets you binary-search down the tree for the leftmost bin whose remaining capacity is >= x (descend left whenever the left child's max >= x), then point-update that leaf and pull the maxima back up — each placement is O(log n).

Constraints

• 1 <= n + k <= 2*10^5
• 0 <= items[i], caps[j]
• Items must be processed strictly in the given order.
• Each item goes into the leftmost (smallest index) bin with remaining capacity >= its size.

Examples

Example 1

Input: ([2, 3, 5], [4, 6, 2])
Output: 1

Explanation: 2->bin0([2,6,2]); 3->bin1([2,3,2]); 5-> no bin has >=5 left, so 1 unplaced.

Example 2

Input: ([5, 5, 5], [4, 4, 4])
Output: 3

Explanation: No bin can hold a size-5 item, so all 3 items are unplaced.

Hints

1. A linear scan per item is O(nk) — too slow at 210^5. You need to find the leftmost bin with capacity >= x in O(log n).
2. Build a max segment tree over the bins' remaining capacities. The root holds the maximum remaining capacity; if it is < x, the item is unplaceable.
3. To find the leftmost fitting bin, descend from the root: go to the left child whenever its subtree max >= x, otherwise go right. This lands on the smallest index whose remaining capacity >= x.
4. After placing, subtract x at that leaf and recompute maxima on the path back to the root — O(log n) per placement.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You are given k items with sizes items[0..k-1] and n bins with initial capacities caps[0..n-1]. Process items in order; for each size x, place it into the leftmost bin whose remaining capacity is at least x, then reduce that bin’s remaining capacity by x. If no such bin exists, the item remains unplaced. Return the number of unplaced items. Design an algorithm that supports up to 2×10^5 items and bins in total with O((n + k) log n) time, describing the data structure you would use.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.