hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Maximum Bags With Full Capacity of Rocks
Problem: 2279. Maximum Bags With Full Capacity of Rocks
Problem Link: leetcode.com/problems/maximum-bags-with-full-capacity-of-rocks/
Companies Asked: Amazon
Approach:
First off, from each bag i, subtracted the rocks[i] from capacity[i].
Now sorted the required capacity.
For each i bag, if the required capacity is lesser than additonalRocks then increased the count by 1 and reduced the additionalRocks by required[i].
Once the additionalRocks gets lesser than the required capacity of i'th bag, then gets out of the loop.
Returned the count.
Time and Space Complexity:
Time Complexity: O(Nlog2N)
Space Complexity: O(N)
Code [C++]
class Solution {
public:
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
int n = capacity.size();
for(int i=0; i<n; i++){
capacity[i] -= rocks[i];
}
sort(capacity.begin(), capacity.end());
int count = 0;
for(int i=0; i<n; i++){
if(!capacity[i]) count++;
else if(capacity[i] <= additionalRocks) {count++, additionalRocks -= capacity[i];}
else break;
}
return count;
}
};