### DhruvBohara's blog

By DhruvBohara, history, 6 months ago,

John has invested in this great app designed by Big Head that can help scale big restaurants: The restaurants have N customers which are represented by an array A of size N*3 where arrival time, departure timer, and the number of dishes X ordered by the customer are denoted by the row of array A

The app calculates the minimum number of chefs the restaurant needs to hire to make dishes to fulfill the orders of all N customers. One chef can only make one dish in one unit of time and each dish takes a unit of time to be prepared.

Help John to determine the minimum number of chefs required

to fulfill the orders of all the N customers.

Parameters description

N. Represents the number of customers

A Represents the array that denotes the details of the N customers

Constraints: 1<=N <=2*10^5 1<=l<=r<=10^9 1<=X<=10^9

• -3

 » 6 months ago, # |   0 Auto comment: topic has been updated by DhruvBohara (previous revision, new revision, compare).
 » 6 months ago, # |   0 Try to come up with a solution in $O(r)$: say you have $k$ chefs, which dishes should they prepare at $t=0,1,\ldots$? Then try to find a way to optimize it to be faster, $O(n)$ or similar.
 » 6 months ago, # |   +3 Maybe we can do it like, sort by the right endpoints. Let's say we have to check whether $x$ number of chefs are enough, then what you can do is at each time $t$, you can keep making $x$ orders and whenever a right endpoint occurs, you subtract the desired number of orders from them. Now we just have to check if this can always been done. Spoilervoid solve(){ int n; cin >> n; vector> a(n, vector(3, 0)); vector> vp; vp.push_back({-1, 0}); for (int i = 0; i < n; i += 1) { cin >> a[i][0] >> a[i][1] >> a[i][2]; vp.push_back({a[i][1], a[i][2]}); } sort(vp.begin(), vp.end()); auto check = [&] (int mid) { int dishes = 0; for (int i = 1; i <= n; i += 1) { dishes += (vp[i].first - vp[i - 1].first) * mid; if (vp[i].second > dishes) return false; else dishes -= vp[i].second; } return true; }; int l = 0, r = 1e9; while (r - l > 1) { int mid = (l + r) / 2; if (!check(mid)) l = mid; else r = mid; } cout << r << endl; } 
•  » » 6 months ago, # ^ |   0 So , are we assuming that food can be prepared in advance ,i.e. before a person arrives??
•  » » » 6 months ago, # ^ |   0 yes.