You are running an IPO auction to distribute a fixed number of shares among interested investors. In an IPO auction, the final price is not preset; instead, potential buyers submit bids stating how many shares they want and the price they are willing to pay. Shares are then allocated starting from the highest bidders until all shares have been assigned.
Before the auction closes, bidders submit their offers, each specifying a user ID, the number of shares requested, a bid price, and a timestamp. After all bids are collected, the allocation process begins:
Allocation proceeds in multiple rounds, working from the highest bid price downward. In each round, the bids with the current highest price are identified, shares are assigned to those bidders, and the processed bids are removed:
If only one bidder has the highest price, that bidder receives the number of shares they requested (or the remaining unallocated shares if there aren't enough to cover the full request).
If multiple bidders share the same highest price, shares are distributed among them round‑robin style: one share at a time, looping through the bidders ordered by timestamp (earliest first). When a bidder receives their full requested amount, they drop out of the round‑robin rotation. The process continues until every bidder in that price group has been satisfied or all remaining shares are exhausted, whichever happens first.
After the allocation is complete, return a list of user IDs of the bidders who received no shares, sorted in ascending order.
You are given the function signature:
public static List<Integer> allocate_shares(List<List<Integer>> bids, int totalShares)
Example 1:
Input: bids = [[1, 1, 101, 0], [1, 2, 100, 1], [2, 4, 100, 2], [3, 1, 99, 3], [4, 2, 100, 4]], totalShares = 3
Output: [3, 4]
Explanation:
bids = [[1,1, 101, 0], [1, 2, 100, 1], [2, 4, 100, 2], [3, 1, 99, 3], [4, 2, 100, 4]] totalShares = 3
[3,4]
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | User | Shares | Price | Time |
| 1 | 1 | 1 | 101 | 0 |
| 2 | 1 | 2 | 100 | 1 |
| 3 | 2 | 4 | 100 | 2 |
| 4 | 3 | 1 | 99 | 3 |
| 5 | 4 | 2 | 100 | 4 |
We have 5 bids and 3 total shares to allocate. Each bid has a user ID, shares requested, bid price, and timestamp.
Example 2:
Input: bids = [[1, 10, 100, 5], [2, 10, 90, 1]], totalShares = 5
Output: [2]
Example 3:
Input: bids = [[1, 2, 100, 1], [2, 2, 100, 2]], totalShares = 3
Output: []
Constraints:
0 < totalShares ≤ 10^30 < bids.length ≤ 10^5sharesRequested, bidPrice > 0timestamp is unique within the inputbids = [[1,1, 101, 0], [1, 2, 100, 1], [2, 4, 100, 2], [3, 1, 99, 3], [4, 2, 100, 4]] totalShares = 3
[3,4]
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | User | Shares | Price | Time |
| 1 | 1 | 1 | 101 | 0 |
| 2 | 1 | 2 | 100 | 1 |
| 3 | 2 | 4 | 100 | 2 |
| 4 | 3 | 1 | 99 | 3 |
| 5 | 4 | 2 | 100 | 4 |
We have 5 bids and 3 total shares to allocate. Each bid has a user ID, shares requested, bid price, and timestamp.