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.

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.

Got it, thank you :-)

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

Thank You:-)

Suppose n = 1e5

t[i] = 10 for all 0<=i<n

M = 11

Now while iterating you reach i = 1e5, you have 1e5 elements in your priority queue. Your while loop runs 1e5 times as you will have to pop all elements of the priority queue except last one.

So in the worst case, the complexity is n^2 log n

Got it, it should be m instead of tmax, :-)