Restaurant Customers

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
Deutsche BankExpedia Group

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
2
1 3
4 5
Sample Output 1 :
1
Explanation For Sample Input 1 :
Customer 1 arrives at ‘1’ and leaves at ‘3’. So, the maximum number of customers at that time is only ‘1’. Now the 2nd customer arrives at ‘4’ and leaves at ‘5’. So, the maximum number of customers remains ‘1’ only.
Sample Input 2 :
1
2
2 5
1 3
Sample Output 2 :
2
Hint

Try to find for each time individually.

Approaches (2)
Brute-Force
  • 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.
Time Complexity

O(M * N), where ‘N’ is the number of customers, and ‘M’ is 10^6.

 

We are running a loop through all the possible unit times. In each iteration, we are traversing through all the customer’s data that of size N. In the worst-case the final leaving time, let it be M would be 10^6. So, the time complexity will be O(M*N).

Space Complexity

O(1)

 

As we are only using constant space.

Code Solution
(100% EXP penalty)
Restaurant Customers
Full screen
Console