Maximum Price to Fill a Bag — LeetCode 2548 Python Solution
MediumLeetCode PremiumGreedyArraySorting
- Problem
- #2548
- Pattern
- Greedy
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 2D integer array items where items[i] = [pricei, weighti] denotes the price and weight of the ith item, respectively. You are also given a positive integer capacity.
Example
- Input
- items = [[50,1],[10,8]], capacity = 5
- Output
- 55.00000
- Explanation
- We divide the 2nd item into two parts with part1 = 0.5 and part2 = 0.5.
Python solution
Python
class Solution:
def maxPrice(self, items: List[List[int]], capacity: int) -> float:
ans = 0
for p, w in sorted(items, key=lambda x: x[1] / x[0]):
v = min(w, capacity)
ans += v / w * p
capacity -= v
return -1 if capacity else ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(\log n), where n is the number of items auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2548. Maximum Price to Fill a Bag 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
Frequently asked questions
- How hard is LeetCode 2548. Maximum Price to Fill a Bag?
- LeetCode 2548. Maximum Price to Fill a Bag is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2548. Maximum Price to Fill a Bag?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 2548. Maximum Price to Fill a Bag?
- The Python solution on this page uses O(\log n), where n is the number of items auxiliary space.
- What topics does LeetCode 2548. Maximum Price to Fill a Bag cover?
- LeetCode 2548. Maximum Price to Fill a Bag is tagged Greedy, Array and Sorting on LeetCode.
- Is LeetCode 2548. Maximum Price to Fill a Bag a premium problem?
- Yes. LeetCode 2548. Maximum Price to Fill a Bag is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.