Minimum Partitions to Hold All Data

Problem Given used[] (data currently on each partition) and totalCapacity[] (capacity of each partition), data can be freely moved between partitions. Return the minimum number of partitions that can hold all the data without any partition exceeding its capacity.

Input / Output

• Input: int arrays used and totalCapacity (same length).
• Output: minimum partition count.

Constraints

• Up to 10^5 partitions; O(n log n) expected.

Example

• used = [3,2,1,3,1], totalCapacity = [3,5,3,5,5] → 2 (total data 10; two capacity-5 partitions suffice).

Expected approach

• The data is fluid, so only the total matters: D = Σ used. Sort capacities descending and take the largest ones greedily until their sum ≥ D; the count taken is the answer. O(n log n) time. Justify the greedy (any feasible set of k partitions is dominated by the k largest capacities). Edge: D = 0 → 0 partitions.