#include #include #include #include #include using namespace std; class Solution { public: int getMinShoppers(vector> orders, double k) { if (orders.size() == 0) { return 0; } int totalDuration = 0; for (vector& order : orders) { totalDuration += order[0]; } if (((double) totalDuration) / orders.size() > k) { return -1; } // Sort orders by the time they are received, if received time is the same, we want short order be processed first sort(orders.begin(), orders.end(), [](const vector& a, const vector& b) { if (a[1] == b[1]) { return a[0] < b[0]; } else { return a[1] < b[1]; } }); // Binary search to find the minimum number of shoppers int lo = 1, hi = orders.size(); while (lo < hi) { int mid = (lo + hi) / 2; double avgTime = getAverageWaitTime(orders, mid); if (avgTime <= k) { hi = mid; } else { lo = mid + 1; } } return lo; } private: double getAverageWaitTime(vector>& orders, int shoppers) { priority_queue, greater> pq; // min heap to store the end time of each shopper int totalWait = 0, start = orders[0][1]; for (int i = 0; i < orders.size(); i++) { int duration = orders[i][0]; int arrive = orders[i][1]; while (!pq.empty() && pq.top() <= arrive) { pq.pop(); } if (pq.size() == shoppers) { start = pq.top(); // Poll the earliest finished order, then we can start proceed the next order immediately pq.pop(); } // If we have finished all the orders, we can start the next order immediately start = max(start, arrive); int finished = start + duration; pq.push(finished); totalWait += (finished - arrive); } return ((double) totalWait) / orders.size(); } };

AI Assistant