QUEUE2 - EDITORIAL (Unofficial)

PROBLEM LINK:

Practice
Contest

Author: kingofnumbers
Editorialist: admin5

DIFFICULTY:

Easy

PREREQUISITES:

Basic implementation, Greedy

PROBLEM:

At T = 0, you are given M people in queue, and N more people gonna come at their given time A[1], A[2] … A[N], and in each L time unit restaurant will become vacant and the person currently at the front of the queue takes it, you need to find minimum time you have to spend standing in the queue.

QUICK EXPLANATION:

  • Sort the time at people come in ascending order.
  • Calculate wating time only when a person come (A[i]) and at T = 0 and T = K as well.

EXPLANATION:

Calculate the wating time only when a person come instead of every value of K because you can enter in restaurant when restaurant become vacant, at T = 0 there is already M people in queue so we can’t enter in between them, that’s why it is sufficient to check only when a person come.

First sort the given array A of arriving times of people.
You can calculate the waiting time at any point of T let suppose when T = X.

Waiting time at X = (M - (T / L)) * L + (L - (T % L)) iff (M - (T / L)) \geq 0
otherwise waiting time at X = 0

[//]: # (% in it we add (L - (T % L)) iff (M - (T / L)) > 0 )

and increase M by 1 when a person come after calculating the waiting time for that particular time T because we can stand in queue before him.

So just need to find minimum waiting time.

Time Complexity

Time complexity is O(N*log(N)) per test case.

SOLUTIONS:

Editorialist’s solution can be found
here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like

Your solution gives the output for the below test case as -60, the answer should be 0.
1 2 100 10
20

2 Likes

The problem had a lot of weak test cases. Our code (which we eventually figured out had a lot of bugs) got 50 points (Subtask I) very easily, despite the fact that it was failing on 3-4 test cases.

Why do we need to calculate the waiting time at t=0 as well ?

Very nice editorial!! Thank you for taking time to write it :slight_smile:

Yeah you point it out correctly, and I’ll fix it soon. So this means there is weak test cases in this question as well.

this issue has been fixed, thanks to point it out.

it could be the case we can get minimum waiting time at 0

Could you please provide me any such test case ?

Yeah there is no need to check at T = 0. :wink:

Thanks! :slight_smile:

Oops, tagging someone here does not send a notification.

Yeah I am also facing the same problem, I don’t know why I am not getting notification of any updates. :frowning: