Problem Brief

Initial Public Offering

FULLTIMEOA

A company launches an initial public offering (IPO) where investors submit bids during a bidding window. Each bid is represented as [userId, numberOfShares, biddingPrice, timestamp].

After the bidding window closes, shares are allocated from the highest price downward until no shares remain.

Allocation rules

If one bidder has the highest price, that bidder receives as many requested shares as possible.
If multiple bidders share the same highest price, allocate one share at a time in ascending timestamp order.
Once a bidder receives all requested shares, remove that bidder from the round-robin process.
Continue within the price group until either all bidders in that group are satisfied or no shares remain, then move to the next lower price.

Return the user IDs of every bidder who receives no shares at all, sorted in ascending order.

Function Description

Complete getUnallottedUsers.

getUnallottedUsers has the following parameters:

int[][] bids: each row is [userId, shares, price, timestamp]
int totalShares: the total number of shares available in the IPO

Returns: int[] of user IDs that received no shares, sorted in ascending order.

1Example 1

Input

bids = [[1,5,7,0],[2,7,8,1],[3,7,7,2],[4,10,6,3]], totalShares = 18

Output

[4]

Explanation

User 2 has the highest bid price and receives 7 shares first. The remaining 11 shares go to the price-7 group containing users 1 and 3, allocated one share at a time by timestamp. User 1 receives all 5 requested shares, user 3 receives the remaining 6, and user 4 receives no shares.

2Example 2

Input

bids = [[1,2,5,0],[2,2,5,1],[3,1,4,2]], totalShares = 2

Output

[3]

Explanation

Users 1 and 2 tie for the highest price. The two available shares are distributed round-robin by timestamp, so each receives one share. The lower-priced bid from user 3 is never reached and that user is returned.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10^5
1 <= totalShares <= 10^9
Each bid row contains exactly four integers: [userId, shares, price, timestamp].
timestamp values are strictly increasing in the original input order.
User IDs in the result must be sorted in ascending order.