Skip to content

2548. Maximum Price to Fill a Bag 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  double maxPrice(vector<vector<int>>& items, int capacity) {
    double ans = 0;

    // Sort items based on price/weight.
    sort(items.begin(), items.end(),
         [](const vector<int>& a, const vector<int>& b) {
      return static_cast<double>(a[0]) / a[1] >
             static_cast<double>(b[0]) / b[1];
    });

    for (const vector<int>& item : items) {
      const int price = item[0];
      const int weight = item[1];
      // The bag is filled.
      if (capacity <= weight)
        return ans + price * capacity / static_cast<double>(weight);
      ans += price;
      capacity -= weight;
    }

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public double maxPrice(int[][] items, int capacity) {
    double ans = 0;

    // Sort items based on price/weight.
    Arrays.sort(items, new Comparator<int[]>() {
      @Override
      public int compare(int[] a, int[] b) {
        return Double.compare((double) b[0] / b[1], (double) a[0] / a[1]);
      }
    });

    for (int[] item : items) {
      final int price = item[0];
      final int weight = item[1];
      // The bag is filled.
      if (capacity <= weight)
        return ans + price * capacity / (double) weight;
      ans += price;
      capacity -= weight;
    }

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maxPrice(self, items: List[List[int]], capacity: int) -> float:
    ans = 0

    # Sort items based on price//weight.
    for price, weight in sorted(items, key=lambda x: -x[0] / x[1]):
      # The bag is filled.
      if capacity <= weight:
        return ans + price * capacity / weight
      ans += price
      capacity -= weight

    return -1