This approach involves calculating how many rocks each bag needs to be full. Then, we sort these requirements in increasing order. By doing so, we ensure we fill the bags requiring fewer rocks first, maximizing the number of fully filled bags. We iterate through these sorted requirements, and while we have enough additional rocks, we fill these bags, counting the number of bags that can be fully filled.
Time Complexity: O(n log n), due to sorting the differences.
Space Complexity: O(n), for storing the differences array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int maxBagsFull(int* capacity, int* rocks, int additionalRocks, int n) {
9 int diffs[n];
10 for (int i = 0; i < n; i++) {
11 diffs[i] = capacity[i] - rocks[i];
12 }
13 qsort(diffs, n, sizeof(int), cmpfunc);
14 int count = 0;
15 for (int i = 0; i < n; i++) {
16 if (additionalRocks >= diffs[i]) {
17 additionalRocks -= diffs[i];
18 count++;
19 } else {
20 break;
21 }
22 }
23 return count;
24}This C implementation calculates rock deficits for each bag, sorts using `qsort`, then iteratively fills them using available additional rocks, maximizing the count of full bags.
Instead of sorting the entire list of differences, we can use a min-heap (priority queue) to keep track of the current smallest difference that can be fulfilled with the additional rocks. This way, we continuously fill the bags requiring the least rocks at the minimum overhead cost of tree-based structure operations. While more sophisticated, this method matches the efficiency of the sorting approach for this problem's expected input size.
Time Complexity: O(n log n), predominantly due to building and maintaining the heap.
Space Complexity: O(n), for the heap storage.
1import java.util.PriorityQueue;
2
3class Solution {
4 public int maxBagsFull(int[] capacity, int[] rocks, int additionalRocks) {
5 PriorityQueue<Integer> pq = new PriorityQueue<>();
6 for (int i = 0; i < capacity.length; i++) {
7 pq.offer(capacity[i] - rocks[i]);
8 }
9 int count = 0;
10 while (!pq.isEmpty() && additionalRocks >= pq.peek()) {
11 additionalRocks -= pq.poll();
12 count++;
13 }
14 return count;
15 }
16}This Java implementation employs a priority queue to always efficiently choose and fulfill the bag that has the least number of additional rocks required, thereby maximizing the number of bags filled to capacity.