LeetCode: 2279-Maximum Bags With Full Capacity of Rocks 解題紀錄

Last Updated on 2022-12-27 by Clay

題目

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

---

解題紀錄

優先權佇列 (Priority Queue)

首先，我會把當前計算的背包空間減去當前空間中石頭的數量，取得這一個背包空間剩餘的容量。這個剩餘的容量我會儲存在從小排到大的優先權佇列中，碰到 0 時則要記得把已經填滿的背包數加 1。

接著就是把可以填充的石頭數量從小容量的背包開始填充起，填到沒有容量為止，回傳累計的填滿包數。

優先權佇列 (Priority Queue) 複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        // Init
        int bag = 0;
        priority_queue<int, vector<int>, greater<int>> losses;

        // Record the losses
        for (int i=0; i<rocks.size(); ++i) {
            int loss = capacity[i] - rocks[i];
            if (loss != 0) {
                losses.push(loss);
            }
            else {
                ++bag;
            }
        }

        // Fill the bags
        while (!losses.empty()) {
            additionalRocks -= losses.top();
            losses.pop();
            ++bag;

            if (additionalRocks < 0) {
                --bag;
                break;
            }
        }
        
        return bag;
    }
};

Python 範例程式碼

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        # Init
        bag = 0
        losses = [capacity[i]-rocks[i] for i in range(len(rocks))]

        # Sort
        losses.sort()

        # Fill the bag
        for loss in losses:
            additionalRocks -= loss
            if additionalRocks >= 0:
                bag += 1
            else:
                break
        
        return bag

---

References

• 2279. Maximum Bags With Full Capacity of Rocks

---

Read More

• LeetCode 解題紀錄目錄