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 0-indexed 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/maximum-bags-with-full-capacity-of-rocks/

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).

All Problems

All Solutions