Allocate limited inventory items based on a priority algorithm.
During a flash sale on Amazon, customers submit requests for a limited quantity of a product. Each request includes:
[customerId, quantity, bidAmount, timestamp]
Items are allocated using these rules:
- Higher bids get priority.
- If multiple customers have the same bid, allocate items in round-robin order based on the earliest timestamp until all inventory is allocated.
- A customer gets one item per round until their request is fulfilled.
Return the IDs of customers who received no items.
Note: Round-robin allocation means cycling through the tied customers in order of their timestamps, granting exactly one item to each customer per cycle, until either the inventory runs out or all requested quantities are fulfilled.
Example
Input:
requests = [[1, 5, 5, 0], [2, 7, 8, 1], [3, 7, 5, 1], [4, 10, 3, 3]]
totalInventory = 18Output:
[4]Explanation: The first three requests have a higher bidding amount than the 4th request, and the total quantity requested in the first three requests is 19, whereas the available inventory is 18, so only one customer is left without any allocation: customer ID 4.
This problem asks you to allocate a limited inventory by bid priority, then break ties fairly using timestamp-based round-robin distribution. The key idea is to sort requests by bid in descending order, group customers with the same bid, and simulate one item per customer per cycle until inventory runs out or all requests are satisfied. After allocation, return the customer IDs that received nothing. The main challenges are handling tie groups correctly and tracking which customers were never assigned an item.
