### Ashish's blog

By Ashish, history, 5 years ago,

Hey there,
Problem
My Solution
I wrote a solution which uses priority queue and pops the maximum element until the sum of elements inside the priority queue is greater than (m-ti) for all 1<=i<=n, so the running time (according to me) is n*logn*max(ti) as at every pop operation the sum will reduce by atleast 1 (1<=ti<=100), logn for priority queue operations and total of n students.
When I submitted the code, it gave me TLE on test #14.
Any help is appreciated.
Thank You.

• 0

 » 5 years ago, # | ← Rev. 2 →   0 Consider the following test case. n = 2*10^5 , m = 100, time that a student spends to answer to a ticket is 100 for all students. The number of pop operations would be much greater than you counted in your time complexity.
•  » » 5 years ago, # ^ |   +6 Got it, thank you :-)
 » 5 years ago, # | ← Rev. 2 →   +12 Here is my submission, I have also used Priority queues(PQ). But I have used two priority queues one minPQ and one maxPQ, instead of your removed vector.You can go thru my submission
•  » » 5 years ago, # ^ |   0 Thank You:-)
 » 5 years ago, # | ← Rev. 3 →   +3 Suppose n = 1e5t[i] = 10 for all 0<=i
•  » » 5 years ago, # ^ |   +3 Got it, it should be m instead of tmax, :-)