Maximize revenue from inventory sales
Problem
A store manages n distinct products. For each product i (0-indexed), an integer quantity[i] specifies the number of units currently in stock.
The store expects m customers. Each customer will purchase exactly one unit of a product, provided it is in stock (a product with zero stock cannot be sold).
Pricing Rule:
- When a customer buys one unit of product
i, the price paid is equal to the current remaining stock of productibefore the purchase. - Immediately after the purchase, the stock of product
idecreases by 1 (i.e.,quantity[i]--). - For example, if product
ihas 5 units in stock when a customer arrives and chooses to buy it, that customer pays 5, and the stock for productibecomes 4 for subsequent customers.
The store's objective is to maximize its total revenue by strategically choosing which product to sell to each customer (among those with positive stock).
If the total number of units across all products is less than m, then at most the total available stock can be sold. Any remaining customers beyond that point cannot make a purchase.
Input
- An integer
n– the total number of different products. - An array
quantityof lengthn, wherequantity[i]is a non-negative integer representing the initial stock of producti. - An integer
m– the number of customers, each buying at most one unit as described.
Output
Return a single integer representing the maximum total revenue the store can achieve by optimally selecting products for sale.
Your algorithm should be efficient enough to handle large values of n, m, and individual product quantities.
Example
Consider the following scenario:
n = 2quantity = [2, 3]m = 3
An optimal sequence of sales to maximize revenue is:
- Customer 1 buys from product 1 (which has 3 units in stock) → pays 3. Stock becomes
[2, 2]. - Customer 2 buys from product 0 (which has 2 units in stock) → pays 2. Stock becomes
[1, 2]. - Customer 3 buys from product 1 (which has 2 units in stock) → pays 2. Stock becomes
[1, 1].
The total revenue generated is 3 + 2 + 2 = 7, which is the maximum possible.
AI interview prep
Core dilemma
Balancing the immediate maximum gain (selling the highest-priced item) with the dynamic impact of reducing that item's future price, to achieve a globally optimal total revenue. This is a dynamic greedy optimization problem where local choices affect future options.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Maximize revenue from inventory sales
Problem
A store manages n distinct products. For each product i (0-indexed), an integer quantity[i] specifies the number of units currently in stock.
The store expects m customers. Each customer will purchase exactly one unit of a product, provided it is in stock (a product with zero stock cannot be sold).
Pricing Rule:
- When a customer buys one unit of product
i, the price paid is equal to the current remaining stock of productibefore the purchase. - Immediately after the purchase, the stock of product
idecreases by 1 (i.e.,quantity[i]--). - For example, if product
ihas 5 units in stock when a customer arrives and chooses to buy it, that customer pays 5, and the stock for productibecomes 4 for subsequent customers.
The store's objective is to maximize its total revenue by strategically choosing which product to sell to each customer (among those with positive stock).
If the total number of units across all products is less than m, then at most the total available stock can be sold. Any remaining customers beyond that point cannot make a purchase.
Input
- An integer
n– the total number of different products. - An array
quantityof lengthn, wherequantity[i]is a non-negative integer representing the initial stock of producti. - An integer
m– the number of customers, each buying at most one unit as described.
Output
Return a single integer representing the maximum total revenue the store can achieve by optimally selecting products for sale.
Your algorithm should be efficient enough to handle large values of n, m, and individual product quantities.
Example
Consider the following scenario:
n = 2quantity = [2, 3]m = 3
An optimal sequence of sales to maximize revenue is:
- Customer 1 buys from product 1 (which has 3 units in stock) → pays 3. Stock becomes
[2, 2]. - Customer 2 buys from product 0 (which has 2 units in stock) → pays 2. Stock becomes
[1, 2]. - Customer 3 buys from product 1 (which has 2 units in stock) → pays 2. Stock becomes
[1, 1].
The total revenue generated is 3 + 2 + 2 = 7, which is the maximum possible.