Maximize Revenue from Depleting VM Stock
A platform has several VM types with a current stock count for each. Customers arrive one at a time. Each rents one instance from a type with the greatest remaining stock and pays that stock count before it is decremented. Compute total revenue for m customers.
Function Signature
max_vm_revenue(vm_stock: list[int], m: int) -> int
Valid Input Domain
The stock list is nonempty, counts are nonnegative integers, and m is between zero and the total stock. The result fits in signed 64-bit range.
Exact Output Semantics
At each sale, use the current maximum positive stock as the price, then reduce one type having that stock by one. If several types tie, any may be chosen because their equal decrement produces the same multiset and total. Return the exact total revenue.
Constraints
-
1 <= vm_stock.length <= 200,000.
-
0 <= vm_stock[i] <= 10^9.
-
0 <= m <= sum(vm_stock).
-
The result fits in signed 64-bit range.
Public Examples
Example 1
Input: vm_stock = [1, 2, 4], m = 4
Output: 11
The successive maximum prices are 4, 3, 2, and 2.
Example 2
Input: vm_stock = [2, 2], m = 3
Output: 5
The sale prices are 2, 2, and 1 regardless of which tied type is chosen first.
Hints
-
Only current stock levels influence future prices; VM type identity does not.
-
Consider processing repeated stock levels together when m is much larger than the number of types.