DhruvBohara's blog

By DhruvBohara, history, 6 months ago, In English

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

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DhruvBohara (previous revision, new revision, compare).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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.

Spoiler
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So , are we assuming that food can be prepared in advance ,i.e. before a person arrives??