Last Updated: 21 Apr, 2021
Restaurant Customers
Moderate
Asked in companies
Ninja is the manager of a restaurant. There were ‘N’ customers who visit the restaurant. Ninja is interested in calculating what was the maximum number of customers in the restaurant at a time. He finds this problem is tough for him, so he wants your help.
You are given the arrival and leaving time of ‘N’ customers in the form of arrays named ‘ARRIVAL’ and ‘LEAVING’. Your task is to find the maximum number of customers at any point in time.
Note :
All arrival and leaving times are distinct.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a positive integer, ‘N’, denoting the total number of customers.
The next ‘N’ lines of each test case contain 2 integers, ‘x’, and ‘y’, denoting the arrival and leaving time of a customer.
Output Format :
For each test case, print the “maximum number of customers” in the restaurant at a time, as described in the problem statement.
Output for each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘x’ < ‘y’ <= 10^6
Time Limit: 1 second
Approaches
- For each time between 1 to 10^6, we can calculate the number of customers inside the restaurant at that time, and update the answer with the maximum.
- More precisely, we can find the max_element in the array leaving, let it be x and we can use it as an upper bound for the computation.
- Declare a variable ans = 0.
- Run a loop from i = 1 to i < x, in each iteration:
- Create a variable current = 0.
- Run a loop from j = 0 to j < N, in each iteration do:
- If the arrival[j] <= i and leaving[j] > i, then increment current by 1.
- ans = max(ans, current).
- Return the ans.
- The idea here is to use sorting.
- At a particular time, we want to know the count of customers inside the restaurant.
- We can represent arrival time with ‘1’ and leaving time with ‘-1’. So, we just need to add these numbers after sorting and update ans each time with the maximum.
- Create a 2D array named temp[2*N][2]. The first element of the array denotes the arrival/departure time, and the second indicates 1/-1 corresponding to this. In CPP, we can use the vector of pairs for the same.
- Insert all the customer’s data into the array temp.
- Now, sort this array. After sorting, we have all the customer’s data sequentially.
- Create two variables named ans and current. Initialize both with 0.
- Run a loop from i = 0 to i < 2*N, in each iteration do:
- current = current + temp[i][1].
- ans = max(ans, current).
- Finally, return the ans.