Compute total revenue from greedy VM rentals

Problem Statement

You are managing a cloud provider's VM rental system. You have n different VM types, each with a fixed hourly price. You receive a sequence of m rental requests, where each request specifies a VM type and the duration of the rental.

However, there is a constraint: at any given time, you can only rent out a VM if you have the 'optimal' available unit. For this system, the 'optimal' unit is defined as the VM currently available that has the highest price. If multiple units of the same type are available, you always pick the one that has been idle for the longest duration (FIFO) among that type.

Given a list of n VM types with their respective hourly prices and a sequence of m requests (type_id, duration), compute the total revenue generated. If a request cannot be fulfilled because no VMs of that type are available, that request is ignored.

Function Signature

def compute_total_revenue(vm_prices: List[int], inventory: List[int], requests: List[Tuple[int, int]]) -> int:

• vm_prices: A list where index i is the price of VM type i.
• inventory: A list where index i is the initial count of available VMs of type i.
• requests: A list of tuples (type_id, duration).

Examples

Example 1:

• vm_prices = [10, 20, 30], inventory = [1, 1, 1], requests = [(0, 5), (2, 2), (1, 3)]
• Request (0, 5): 1 unit of type 0 rented. Revenue: 1 * 10 * 5 = 50.
• Request (2, 2): 1 unit of type 2 rented. Revenue: 50 + (1 * 30 * 2) = 110.
• Request (1, 3): 1 unit of type 1 rented. Revenue: 110 + (1 * 20 * 3) = 170.
• Output: 170

Constraints

• n (number of types) <= 10^4
• m (number of requests) <= 10^5
• duration <= 100
• Prices are positive integers.