Calculate Revenue from Highest-Inventory VM Sales
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
A provider sells units from several VM inventory types. The price of one unit equals that type's current remaining inventory immediately before the sale. Each customer buys one unit from a type with the greatest current inventory, then that type's inventory decreases by one.
### Function Signature
`vm_revenue(inventory: list[int], customers: int) -> int`
### Output
Return total revenue after serving exactly `customers` customers. Any type tied for greatest inventory may be chosen; the total revenue is unchanged by that tie choice. Types with zero inventory cannot be sold.
### Constraints
- `1 <= len(inventory) <= 200000`.
- `0 <= inventory[i] <= 1000000000`.
- `0 <= customers <= 200000`.
- `customers <= sum(inventory)`.
- Use an integer type large enough for the total revenue, which may exceed a signed 32-bit integer.
- Do not mutate the input array.
### Examples
Input: `inventory = [1,2,4], customers = 4`
Output: `11`
The four sale prices are 4, 3, 2, and 2.
Input: `inventory = [2,2], customers = 3`
Output: `5`
Input: `inventory = [0,3], customers = 0`
Output: `0`
Overview: Sell each VM unit at its current inventory count, always choose a type with maximum inventory, and compute total revenue safely.
A provider sells virtual-machine units from several inventory types. `inventory[i]` is the number of units currently available for type `i`.
Customers are served one at a time. Each customer buys exactly one unit from a type that currently has the greatest remaining inventory. The price of that unit equals that type's remaining inventory immediately before the sale; afterwards, that type's inventory decreases by one. A type whose remaining inventory is zero cannot be sold.
Given `inventory` and an integer `customers`, return the total revenue collected after serving exactly `customers` customers.
If several types are tied for the greatest remaining inventory, any one of them may be chosen. The total revenue is unchanged by that tie choice, so the returned value is unique. Do not mutate the input array.
The total revenue may exceed a signed 32-bit integer, so use a 64-bit integer type (`long` in Java, `long long` in C++).
Example 1:
Input: inventory = [1, 2, 4], customers = 4
Output: 11
Explanation: The four sale prices are 4, 3, 2, and 2. The type that started at 4 is sold down to 2, at which point it ties with the type that started at 2, and the last two customers each pay 2.
Example 2:
Input: inventory = [2, 2], customers = 3
Output: 5
Explanation: Both types start tied at 2, so the prices are 2, 2, and 1 for a total of 5, whichever tied type each customer picks.
Example 3:
Input: inventory = [0, 3], customers = 0
Output: 0
Explanation: No customer is served, so no revenue is collected.
Constraints
- 1 <= len(inventory) <= 200000
- 0 <= inventory[i] <= 1000000000
- 0 <= customers <= 200000
- customers <= sum(inventory)
- Use an integer type large enough for the total revenue, which may exceed a signed 32-bit integer (long in Java, long long in C++); the answer is at most 2 * 10^14 and is exactly representable as a JavaScript number
- Do not mutate the input array
Examples
Input: ([1, 2, 4], 4)
Expected Output: 11
Explanation: Source example 1. Prices are 4, 3, 2, 2; the top value falls to tie the second type partway through, which catches off-by-one errors in partial-level counting.
Input: ([2, 2], 3)
Expected Output: 5
Explanation: Source example 2. Both types are tied at 2, so prices are 2, 2, 1 regardless of which tied type each customer picks.
Hints
- Because the price is always the current greatest remaining inventory, the answer does not depend on which tied type a customer picks - only on the multiset of remaining inventories after each sale.
- customers can be far smaller than sum(inventory), but it can also be much larger than the number of distinct inventory values. Ask how many types share the greatest value at any moment, and how that count changes as the greatest value falls.
- The money collected while one type is sold from a units down to b units is a sum of consecutive integers; a closed form for that sum avoids charging customers one at a time, but remember the budget can run out midway.