PROBLEM LINK:
Author: kingofnumbers
Editorialist: srvptk
DIFFICULTY:
Easy
PREREQUISITES:
Greedy Approach, Maths
PROBLEM:
Initially (T=0), you are given with M people standing in the queue. N more people are coming at time stamps A[1],A[2],…,A[N] . Each person from the queue is removed at timestamps starting in the order L,2L,3L,… and so on. You have to find the minimum time you will spend standing in the queue.
QUICK EXPLANATION:
-
Sort the array A .
-
Compute the waiting time for every A[i] and K. (If you enter the queue at timestamp A[i])
-
Print the minimum waiting time. ( 0 if minimum value is negative)
EXPLANATION:
At T=0, M people are standing in a Queue. The person from the head of the queue is removed at timestamp starting from: L,2L,3L,… and so on.
You have to enter the queue at a timestamp so that you have to wait for minimum time. Moreover you can not enter the queue after timestamp K.
Observation: You will observe that we can find a minimum from the timestamps of entrance time of N people in the Queue or at a timestamp K.
Formula Generation: Suppose you enter at a Timestamp X at which there are Y people already standing in the queue. Then,
Waiting Time = Time taken to process Y people - Timestamp at which you entered the queue
As, first person enters the restaurant at timestamp L and exit the restaurant at 2L. Hence the time taken to process the first person was 2L, similarly for second person from the queue was 3L and so on.
Hence to process Y person from the queue can be calculated through the formula:
Time taken to process Y people = (Y+1)*L
So our generalized formula for calculating the waiting time at timestamp Z will be:
Waiting Time = (Y+1)*L - Z
You have to maintain the total number of people in the queue at a given timestamp (Start with M people initially). I think you can figure it out easily.
The minimum waiting time calculated from the above formula among all timestamps at which N people enters the queue as well as for the Timestamp K will give the required answer.
Note: If the minimum value turns out to be negative then the result will be zero.
TIME COMPLEXITY:
The time complexity is O(N*log(N)) for every case {Due to sorting part}.
SOLUTION:
This is my first editorial so please feel free to share your views and opinions. I will be glad to hear all your reviews.
Thanks