UVa 1203: Argus was a sort of poorly written problem, and I thought it was a lot harder than it actually turned out to be.
Basically, you are given a number of tasks. Each task has an id number and an interval. The interval specifies how often the task returns. You are then given a number k
, and your program must print out the first k
tasks to return in chronological order. This can be done efficiently using a priority queue. We insert pairs of pairs and ints ((t, id), i) into the priority queue, where t is the next time the task will return, i is the interval of the task we are inserting, and id is its id. Since the STL priority queue is a max heap, and we need a min heap, we make all of the entries in the priority queue negative, effectively making it sort in reverse order. Thus the task with the smallest positive t will be at the front of the priority queue, due to the natural sorting order of pairs. For k
iterations, we pop a task off the front of the priority queue, print its id number, add i to t, and push our updated task back into the priority queue.
UVa 1203: Argus
For technical reasons, comments are temporarily unavailable on my posts. If you'd like to discuss this article with me, feel free to email me at or hit me up on Twitter.