How to solve Spoj Printer Queue Problem?
Its simple…and see the constraints are low.
Just maintain a count array where count[i] stores the number of times priority i occurs in the original array. Also maintain a queue of pairs (use
pair< priority, index > to know which index u are dealing with). Start deleting the the elements having priority 9, then 8 , then 7 and so on (deleting process is same as described in the question).
While deleting an element do the following 4 things:-
->Increment a zero initialized variable Time to get the answer.
->Decrement the count array of the current priority you are dealing with.
->If count[i]==0 start deleting priority i-1,
->Output the Time when you delete the index asked in the test case.
There exist more efficient solutions…
1 Like
As @abhikalpu_123 said, the constraints of this problems are pretty low and thus you can solve it in any way you want without worrying about the time complexity of your code.
However our work will reduce a lot if we use the predefined data structures in the STL like:
- queue < pair < priority, index > > : to store the priority and index of the current job.
- priority_queue < priority > : to store the priorities in decreasing order.
Now, just do the things mentioned in the question in your own way.
You can refer to my solution if you get stuck anywhere.
4 Likes