MediumNo. 2279
Maximum Bags With Full Capacity of Rocks — LeetCode 2279 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks.
Example
- 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.
Python solution
class Solution:
def maximumBags(
self, capacity: List[int], rocks: List[int], additionalRocks: int
) -> int:
for i, x in enumerate(rocks):
capacity[i] -= x
capacity.sort()
for i, x in enumerate(capacity):
additionalRocks -= x
if additionalRocks < 0:
return i
return len(capacity)Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2279. Maximum Bags With Full Capacity of Rocks is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2271 | Maximum White Tiles Covered by a Carpet | Medium |
| 0179 | Largest Number | Medium |
| 0324 | Wiggle Sort II | Medium |
| 0452 | Minimum Number of Arrows to Burst Balloons | Medium |
| 0455 | Assign Cookies | Easy |
| 0502 | IPO | Hard |
Frequently asked questions
- How hard is LeetCode 2279. Maximum Bags With Full Capacity of Rocks?
LeetCode 2279. Maximum Bags With Full Capacity of Rocks is rated Medium on LeetCode.
- What topics does LeetCode 2279. Maximum Bags With Full Capacity of Rocks cover?
LeetCode 2279. Maximum Bags With Full Capacity of Rocks is tagged Greedy, Array and Sorting on LeetCode.