Finish the Greatest Number of Partially Filled Bags
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Bag i holds rocks[i] rocks and has total capacity capacity[i]. Distribute up to additionalRocks new rocks among bags without exceeding capacities. Return the largest number of full bags afterward; unused additional rocks are allowed.
```cpp
class Solution {
public:
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks);
};
```
### Examples
**Example 1:**
```text
Input: capacity = [3,5,2], rocks = [3,2,1], additionalRocks = 2
Output: 2
Explanation: The first bag is already full. One rock fills the last bag; the remaining rock cannot fill the middle bag, which needs three.
```
**Example 2:**
```text
Input: capacity = [4,4], rocks = [0,0], additionalRocks = 8
Output: 2
Explanation: Assign four additional rocks to each bag.
```
### Constraints
- Arrays have the same length n, with `1 <= n <= 50000`.
- `1 <= capacity[i] <= 10^9`.
- `0 <= rocks[i] <= capacity[i]`.
- `1 <= additionalRocks <= 10^9`.
### Clarifying Questions
- Do bags that are already full count? Yes.
- Must every additional rock be used? No; unused rocks are allowed.
- Can rocks be moved out of their current bags? No; you may only add new rocks.
- Is the allocation returned? No, return the number of full bags.
```hint Check the boundary
Compare a bag that is already full with one that is one rock short.
```
Overview: Distribute additional rocks without exceeding bag capacities and maximize the number of full bags, counting those already full.