Last Updated: 5 Feb, 2021
Count Customers Who Did Not Get A Computer
Easy
Asked in companies
Mr. X runs an internet cafe which has 'K' computers. His internet cafe has 'N' customers who can come anytime throughout the day. Initially, all the 'K' computers are available for customer use. When a customer enters the cafe he first checks whether any available computer is there. If he finds one he starts using it and it is marked unavailable. When he leaves the cafe that computer is again marked as available. If the customer is not able to find any available computer he leaves the cafe immediately.
You are given an integer array ‘ARR’ in which each value occurs exactly 2 times, the index of the first occurrence of any value denotes the arrival time of the customer while the second occurrence denotes the departing time of the customer. Your task is to find the no. of customers who were not able to find any available computer and had to leave the cafe immediately.
For example :
Consider the sequence of customers as [ 1, 2, 3, 2, 3, 1 ] for N = 3 and K = 2.
The procedure takes place as follows :
1) At the start, Customer 1 comes and finds an available computer and starts using it and now the number of available computers is reduced by 1.
2) Customer 2 comes and he is also able to find an available computer and he starts using the computer. Now all the computers are unavailable.
3) Customer 3 comes and goes back immediately as there are no computers available currently.
4) Customer 2 leaves the cafe making 1 computer available.
5) As customer 3 has already left no new computers are made available.
6) Customer 1 leaves the cafe and all the computers are again available.
As only Customer 3 was unable to find any available computers therefore the answer is 1 for this case.
Input Format :
The first line of the input contains an integer 'T', denoting the number of test cases.
The first line of each test case contains two space-separated integers 'N' and 'K' denoting the number of customers and the number of computers available in the cafe respectively.
The second line of each test case '2*N' space-separated integers denoting the array 'ARR'.
Output Format :
For each test case print the number of customers who left the cafe without using a computer. Print the output of each test case in a new 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^5
1 <= K <= 10^5
1 <= ARR[i] <= N
Time Limit: 1 sec
Approaches
The idea is to store the status of each customer in an extra array and use two variables availableComputers and customersWhoLeft that stores the number of available computers and the number of customers who left because of no available computers respectively.
The status of a customer can have 3 possible values.
- Status = 0, if the customer has not visited till now.
- Status = 1, if the customer was able to find an available computer and is currently using it.
- Status = -1, if the customer has left the cafe.
Steps :
- If the number of computers is greater than or equal to the number of customers, then we will return 0 as in this case all customers will be able to find an available computer irrespective of the sequence with which they come and leave.
- Initialize an array customerStatus having N+1 elements to store the status of each customer. Initialize all values with 0. As initially, no customer has visited the cafe. We are using N+1 elements as we are considering 1-indexing.
- Set availableComputers as K and customersWhoLeft as 0.
- Iterate from i = 0 to 2 * N - 1
- If customerStatus [ARR[i]] is equal to 0 then
- If availableComputers is greater than 0 then decrease availableComputers by 1 and set customerStatus[ARR[i]] as 1.
- Otherwise, increase customersWhoLeft by 1 and set customerStatus[ARR[i]] as -1. We are setting the status as -1 here as the customer will leave the cafe immediately in this case.
- Otherwise, If customerStatus [ARR[i]] is equal to 1 then increase availableComputers by 1 and set customerStatus [ARR[i]] as -1. In this case, the customer has used the computer and has left the cafe after using it.
- Otherwise, If customerStatus [ARR[i]] is equal to -1 then we do not have to do anything as the customer has already left the cafe.
- If customerStatus [ARR[i]] is equal to 0 then
- Return customersWhoLeft as the final answer.