Skip to content

4014. Minimum Total Price After Applying Discounts

Description

You are given two integer arrays prices and discounts.

The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.

You may apply discounts subject to the following rules:

  • Each discount can be applied to at most one item.
  • Each item can receive at most one discount.
  • An item may also receive no discount.

If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.

Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.

Β 

Example 1:

Input: prices = [10,30,21], discounts = [50,60]

Output: 32.50000

Explanation:

  • Apply discounts[1] = 60 to prices[1] = 30, thus 30 * (100 - 60) / 100 = 12.
  • Apply discounts[0] = 50 to prices[2] = 21, thus 21 * (100 - 50) / 100 = 10.5.
  • prices[0] = 10 receives no discount, so it stays 10.

The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.

Example 2:

Input: prices = [100,70], discounts = [10,40,50]

Output: 92.00000

Explanation:​​​​​​​

  • Apply discounts[2] = 50 to prices[0] = 100, thus 100 * (100 - 50) / 100 = 50.
  • Apply discounts[1] = 40 to prices[1] = 70, thus 70 * (100 - 40) / 100 = 42.

The total is 50 + 42 = 92.00000, which is the minimum possible.

Example 3:

Input: prices = [7,3,9], discounts = [100,100]

Output: 3.00000

Explanation:

  • Apply discounts[0] = 100 to prices[2] = 9, thus 9 * (100 - 100) / 100 = 0.
  • Apply discounts[1] = 100 to prices[0] = 7, thus 7 * (100 - 100) / 100 = 0.
  • prices[1] = 3 receives no discount, so it stays 3.

The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.

Β 

Constraints:

  • 1 <= prices.length, discounts.length <= 105
  • 1 <= prices[i] <= 105
  • 1 <= discounts[j] <= 100

Solutions

Solution 1: Greedy + Sorting

To minimize the total price, we need to maximize the total amount saved by discounts. Applying a discount \(d\) to an item with price \(p\) saves \(p \times d / 100\). By the rearrangement inequality, applying larger discounts to more expensive items maximizes the total savings.

Therefore, we sort both \(\textit{prices}\) and \(\textit{discounts}\) in ascending order, then use two pointers starting from the ends of both arrays, repeatedly applying the current largest discount to the current most expensive item and accumulating the discounted price. Once all discounts are used up, the remaining items are added at their original prices.

The time complexity is \(O(n \times \log n + m \times \log m)\), and the space complexity is \(O(\log n + \log m)\). Here, \(n\) and \(m\) are the lengths of the arrays \(\textit{prices}\) and \(\textit{discounts}\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minPrice(self, prices: list[int], discounts: list[int]) -> float:
        prices.sort()
        discounts.sort()
        i, j = len(prices) - 1, len(discounts) - 1
        ans = 0
        while i >= 0 and j >= 0:
            ans += prices[i] * (100 - discounts[j]) / 100
            i -= 1
            j -= 1
        while i >= 0:
            ans += prices[i]
            i -= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public double minPrice(int[] prices, int[] discounts) {
        Arrays.sort(prices);
        Arrays.sort(discounts);

        int i = prices.length - 1;
        int j = discounts.length - 1;

        double ans = 0;

        while (i >= 0 && j >= 0) {
            ans += prices[i] * (100 - discounts[j]) / 100.0;
            i--;
            j--;
        }

        while (i >= 0) {
            ans += prices[i];
            i--;
        }

        return ans;
    }
}

 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 minPrice(vector<int>& prices, vector<int>& discounts) {
        sort(prices.begin(), prices.end());
        sort(discounts.begin(), discounts.end());

        int i = prices.size() - 1;
        int j = discounts.size() - 1;

        double ans = 0;

        while (i >= 0 && j >= 0) {
            ans += prices[i] * (100 - discounts[j]) / 100.0;
            i--;
            j--;
        }

        while (i >= 0) {
            ans += prices[i];
            i--;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minPrice(prices []int, discounts []int) float64 {
    sort.Ints(prices)
    sort.Ints(discounts)

    i := len(prices) - 1
    j := len(discounts) - 1

    var ans float64

    for i >= 0 && j >= 0 {
        ans += float64(prices[i]) * float64(100-discounts[j]) / 100.0
        i--
        j--
    }

    for i >= 0 {
        ans += float64(prices[i])
        i--
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minPrice(prices: number[], discounts: number[]): number {
    prices.sort((a, b) => a - b);
    discounts.sort((a, b) => a - b);

    let i = prices.length - 1;
    let j = discounts.length - 1;

    let ans = 0;

    while (i >= 0 && j >= 0) {
        ans += (prices[i] * (100 - discounts[j])) / 100;
        i--;
        j--;
    }

    while (i >= 0) {
        ans += prices[i];
        i--;
    }

    return ans;
}

Comments