Inventory Allocation with Bids and Round-Robin Amazon OA

You are given an integer totalInventory representing the total number of items available.

You are also given a 2D array requests, where each request is represented as:

[customerId, quantity, bidAmount, timestamp]

where:

customerId — unique ID of the customer. quantity — number of items requested by the customer. bidAmount — amount the customer is willing to pay for each item. timestamp — time at which the request was placed. A smaller timestamp means the request was placed earlier. Allocation Rules Customers with a higher bid amount have higher priority. Customers with the same bid amount are served in increasing order of timestamp. Within the same bid group, allocation happens in a round‑robin manner: Each customer receives at most one item per round. A customer stops participating once their requested quantity has been fulfilled. Continue until either all requests in the bid group are fulfilled or the inventory runs out. Once the inventory is exhausted, no customer from a lower bid group can receive an item. Return the IDs of all customers who received zero items, sorted in ascending order. Constraints 1 <= requests.length <= 10^4 1 <= customerId, quantity, bidAmount, timestamp < 10^8 1 <= totalInventory < 10^8

Example 1 totalInventory = 3

requests = [ [1, 2, 5, 0], [2, 1, 4, 2], [3, 5, 4, 6] ]

Allocation:

Bid 5: Customer 1 → 2 items

Remaining inventory = 1

Bid 4: Customer 2 (timestamp 2) → 1 item Customer 3 (timestamp 6) → 0 items

Therefore:

Output: [3]

Approach

The important observation is that we only need to know which customers received at least one item, not the exact number of items each customer received.

Step 1: Group customers by bid Use:

map<int, vector, greater>

This automatically processes bid groups from highest to lowest.

Step 2: Sort each bid group by timestamp For customers with the same bid, sort them by increasing timestamp.

Step 3: Check the total requested quantity of the group For each bid group:

totalRequested = sum of all quantities in the group

If:

totalRequested <= remainingInventory

then the entire group can be fulfilled.

Therefore, every customer in this group receives at least one item, so add all their IDs to a fulfilled set.

Then:

remainingInventory -= totalRequested

and continue to the next bid group.

Step 4: Handle the first partially fulfilled bid group If:

totalRequested > remainingInventory

then this is the first bid group that cannot be completely fulfilled.

At this point, we only care about who can receive at least one item.

Let: n = number of customers in this bid group

If:

n <= remainingInventory

then every customer can receive at least one item.

Otherwise, only the first remainingInventory customers in timestamp order can receive an item.

After that, inventory is exhausted, so we can stop processing.

#include <bits/stdc++.h>
using namespace std;

struct Req {
    int id;
    int quantity;
    int bid;
    int time;
};

class Solution {
public:
    vector<int> getUnfulfilledCustomers(
        vector<vector<int>> requests,
        long long totalInventory
    ) {
        
        // Group customers by bid in descending order
        map<int, vector<Req>, greater<int>> groups;

        for (auto& r : requests) {
            groups[r[2]].push_back({
                r[0],  // customerId
                r[1],  // quantity
                r[2],  // bid
                r[3]   // timestamp
            });
        }

        // Customers who received at least one item
        unordered_set<int> fulfilled;

        // Process highest bid first
        for (auto& [bid, customers] : groups) {

            if (totalInventory == 0)
                break;

            // Earlier timestamp gets priority
            sort(customers.begin(), customers.end(),
                [](const Req& a, const Req& b) {
                    return a.time < b.time;
                });

            // Calculate total requested quantity for this bid group
            long long totalRequested = 0;
            for (auto& customer : customers) {
                totalRequested += customer.quantity;
            }

            // Entire bid group can be fulfilled
            if (totalRequested <= totalInventory) {
                totalInventory -= totalRequested;
                for (auto& customer : customers) {
                    fulfilled.insert(customer.id);
                }
            } else {
                // First partially fulfilled group
                long long canReceive = min((long long)customers.size(), totalInventory);
                for (int i = 0; i < canReceive; i++) {
                    fulfilled.insert(customers[i].id);
                }
                totalInventory = 0;
                break;
            }
        }

        // Find customers who received zero items
        vector<int> answer;
        for (auto& r : requests) {
            if (fulfilled.find(r[0]) == fulfilled.end()) {
                answer.push_back(r[0]);
            }
        }
        sort(answer.begin(), answer.end());
        return answer;
    }
};