Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2279.html
2279. Maximum Bags With Full Capacity of Rocks
 Difficulty: Medium.
 Related Topics: Array, Greedy, Sorting.
 Similar Questions: Capacity To Ship Packages Within D Days, Maximum Units on a Truck.
Problem
You have n
bags numbered from 0
to n  1
. You are given two 0indexed integer arrays capacity
and rocks
. The ith
bag can hold a maximum of capacity[i]
rocks and currently contains rocks[i]
rocks. You are also given an integer additionalRocks
, the number of additional rocks you can place in any of the bags.
Return** the maximum number of bags that could have full capacity after placing the additional rocks in some bags.**
Example 1:
Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
Output: 3
Explanation:
Place 1 rock in bag 0 and 1 rock in bag 1.
The number of rocks in each bag are now [2,3,4,4].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that there may be other ways of placing the rocks that result in an answer of 3.
Example 2:
Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
Output: 3
Explanation:
Place 8 rocks in bag 0 and 2 rocks in bag 2.
The number of rocks in each bag are now [10,2,2].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that we did not use all of the additional rocks.
Constraints:

n == capacity.length == rocks.length

1 <= n <= 5 * 104

1 <= capacity[i] <= 109

0 <= rocks[i] <= capacity[i]

1 <= additionalRocks <= 109
Solution (Java, C++, Python)

class Solution { public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) { int len = capacity.length; for (int i = 0; i < len; i++) { capacity[i] = rocks[i]; } Arrays.sort(capacity); int total = 0; for (int i = 0; i < len && additionalRocks > 0; i++) { if (capacity[i] <= additionalRocks) { additionalRocks = capacity[i]; total++; } } return total; } } ############ class Solution { public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) { int n = capacity.length; int[] d = new int[n]; for (int i = 0; i < n; ++i) { d[i] = capacity[i]  rocks[i]; } Arrays.sort(d); int ans = 0; for (int v : d) { if (v <= additionalRocks) { ++ans; additionalRocks = v; } else { break; } } return ans; } }

class Solution: def maximumBags( self, capacity: List[int], rocks: List[int], additionalRocks: int ) > int: d = [a  b for a, b in zip(capacity, rocks)] d.sort() ans = 0 for v in d: if v <= additionalRocks: ans += 1 additionalRocks = v return ans ############ # 2279. Maximum Bags With Full Capacity of Rocks # https://leetcode.com/problems/maximumbagswithfullcapacityofrocks/ class Solution: def maximumBags(self, capacity: List[int], rocks: List[int], extra: int) > int: res = 0 A = [] for cap, rock in zip(capacity, rocks): if cap == rock: res += 1 continue A.append(cap  rock) A.sort() for x in A: if extra >= x: res += 1 extra = x else: break return res

class Solution { public: int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) { int n = capacity.size(); vector<int> d(n); for (int i = 0; i < n; ++i) d[i] = capacity[i]  rocks[i]; sort(d.begin(), d.end()); int ans = 0; for (int& v : d) { if (v > additionalRocks) break; ++ans; additionalRocks = v; } return ans; } };

func maximumBags(capacity []int, rocks []int, additionalRocks int) int { n := len(capacity) d := make([]int, n) for i, v := range capacity { d[i] = v  rocks[i] } sort.Ints(d) ans := 0 for _, v := range d { if v > additionalRocks { break } ans++ additionalRocks = v } return ans }

function maximumBags( capacity: number[], rocks: number[], additionalRocks: number, ): number { const n = capacity.length; const diffs = capacity.map((c, i) => c  rocks[i]); diffs.sort((a, b) => a  b); let ans = 0; for ( let i = 0; i < n && (diffs[i] === 0  diffs[i] <= additionalRocks); i++ ) { ans++; additionalRocks = diffs[i]; } return ans; }

impl Solution { pub fn maximum_bags(capacity: Vec<i32>, rocks: Vec<i32>, mut additional_rocks: i32) > i32 { let n = capacity.len(); let mut diffs = vec![0; n]; for i in 0..n { diffs[i] = capacity[i]  rocks[i]; } diffs.sort(); for i in 0..n { if diffs[i] > additional_rocks { return i as i32; } additional_rocks = diffs[i]; } n as i32 } }
Explain:
nope.
Complexity:
 Time complexity : O(n).
 Space complexity : O(n).