Inventory Allocation by Bid Priority

Problem Statement

An e-commerce platform needs to allocate a limited batch of inventory across multiple customer bids. Each bid is represented as [order_id, price, quantity, timestamp], where:

• order_id: A unique positive integer identifying the bid.
• price: The unit price offered by the buyer.
• quantity: The number of units requested.
• timestamp: An integer timestamp indicating when the bid was placed.

You are given an integer total_inventory and a 2D array bids representing all submitted bids. Inventory must be allocated using the following rules:

1. Price Priority: Bids with higher price must be satisfied before bids with lower price.
2. Tier-Level Allocation:
   • If the total remaining inventory is greater than or equal to the total quantity demanded by all bids at the current price tier, each bid in that tier is fully satisfied.
   • If the remaining inventory is strictly less than the total demand at the current price tier, the remaining units are distributed among the bids in that tier in a round-robin fashion:
     • Sort the bids in the current tier by timestamp ascending. If timestamps are identical, break ties by order_id ascending.
     • While inventory remains, iterate through the sorted list of bids in that tier. In each round, allocate 1 unit to each bid that has not yet had its requested quantity fully satisfied.
     • As soon as remaining inventory reaches 0, the allocation process terminates immediately.

Return a list of pairs [order_id, allocated_quantity] sorted by order_id in ascending order. Every submitted bid must appear in the output, even if it received 0 units.

Function Interface

def allocate_inventory(total_inventory: int, bids: list[list[int]]) -> list[list[int]]:
    pass

Constraints

• 0 <= total_inventory <= 10^6
• 1 <= len(bids) <= 10^4
• 1 <= order_id <= 10^9, all order_id values are distinct.
• 1 <= price <= 10^6
• 1 <= quantity <= 10^5
• 1 <= timestamp <= 10^9

Examples

Example 1

Input: 
total_inventory = 10
bids = [
    [1, 100, 4, 10],
    [2, 100, 5, 5],
    [3, 50, 6, 2]
]
Output: 
[[1, 4], [2, 5], [3, 1]]

Explanation:

• Price tier 100 has bids 1 (demands 4) and 2 (demands 5). Total demand is 9, which is <= 10. Both are fully satisfied. Remaining inventory = 10 - 9 = 1.
• Price tier 50 has bid 3 (demands 6). Only 1 unit remains, so bid 3 receives 1 unit.
• Output is sorted by order_id: [[1, 4], [2, 5], [3, 1]].

Example 2

Input: 
total_inventory = 5
bids = [
    [101, 80, 3, 20],
    [102, 80, 2, 10],
    [103, 80, 4, 30]
]
Output: 
[[101, 2], [102, 2], [103, 1]]

Explanation:

• All bids are at price 80. Total demand is 3 + 2 + 4 = 9 > 5, so round-robin allocation is used.
• Sort order by timestamp: Bid 102 (ts 10), Bid 101 (ts 20), Bid 103 (ts 30).
• Round 1: 102 gets 1 (rem 4), 101 gets 1 (rem 3), 103 gets 1 (rem 2).
• Round 2: 102 gets 1 (demands satisfied: 2/2, rem 1), 101 gets 1 (rem 0).
• Inventory reaches 0. Allocation: 101 -> 2, 102 -> 2, 103 -> 1.
• Sorted by order_id: [[101, 2], [102, 2], [103, 1]].

Edge Cases

• total_inventory == 0: All bids receive 0 units.
• Inventory runs out mid-round during round-robin.
• Multiple bids have both the same price and same timestamp.