Problem. Each item type has a current stock inventory[i].
When you sell one unit of a type whose stock is currently x, you earn revenue x, and that stock drops to x - 1.
You must fill exactly orders sales and maximize total revenue.
Example:
inventory = [2, 5]
orders = 4
Optimal sales are priced 5, 4, 3, 2, so the answer is 14.
Return the answer modulo 1_000_000_007.
This is a greedy level-by-level selling problem.
Solution. Sort stock levels descending. Instead of selling one unit at a time, sell whole horizontal layers at once.
If the top width item types all sit at level current, and the next lower level is next_value, then there are width * (current - next_value) units available before the next merge point. Their total value is an arithmetic-series sum.
MOD = 10**9 + 7
def max_revenue(inventory, orders):
levels = sorted(inventory, reverse=True) + [0]
total = 0
width = 1
for index in range(len(levels) - 1):
current = levels[index]
next_value = levels[index + 1]
if current == next_value:
width += 1
continue
drop = current - next_value
sellable = width * drop
if orders >= sellable:
total += width * (current + next_value + 1) * drop // 2
orders -= sellable
else:
full_levels, remainder = divmod(orders, width)
floor = current - full_levels
total += width * (current + floor + 1) * full_levels // 2
total += remainder * floor
return total % MOD
width += 1
return total % MOD
Sorting costs O(n log n). The greedy sweep is linear. Extra space is O(n) for the sorted levels.
Gotchas.
- Always return modulo
1_000_000_007, not only for extreme inputs. - Batch whole levels together; selling one unit at a time is too slow when
ordersis large. - Be careful with the partial-level case when the remaining
ordersdo not consume an entire layer.