Printer Simulation

PQUEUE

The question above was my "SPOJ victory of the day." On my first attempt at the problem I was thinking too hard about all possible cases. Needless to say this resulted in WA. However, today I looked at the problem and noticed that the bounds were extremely low. So I thought about just simulating the process, and realized after a little thinking that this would be O(n^2) in the worst case, which was not a problem considering the fact that the upper bound on n was about 100. After getting my solution accepted I noticed that there were relatively few TLEs, this should have alerted me sooner that a "trivial solution" was possible

I think the problem would be more interesting if they gave you the times that each job was added to the printer queue. The problem would still be solvable by simulation but it would require a little more "creativity" in doing so. However, the way I coded my solution, it wouldn't be too hard to adapt it for this variation. Basically I used a double-ended queue to keep track of the order of each job request. The reason for using this structure is that it has the ability to quickly add and element to the back and delete and element from the front. In addition I used a heap to keep track of which job currently had the highest priority.