A Priority Queue Based on Message Priority and Time Elapsed

Problem:

The aim is to design a custom queue that will pop out a message with the highest priority. Each input message has an already assigned priority value, although this isn’t a fixed value. The priority of each message is incremented after a fixed amount of time has passed.

Solution:

Let's assume that there are a total of 5 different priority levels. 1 to 5, with 1 being the lowest and 5 being the highest. For every 10 minutes a message spends inside the queue, the priority is bumped up by 1 unit. The maximum priority value that can be assigned is 5. In case two elements have the same priority, the messages that have spent the longest in the queue should be popped out first.

A linked list can be used to store the incoming messages. A new message is always added to the end of the list.

To find the element with the highest priority, we need to find an element with the highest summation value of initial priority and time elapsed increments.

The queue would look something like this:

Use a pointer to refer to the first occurrence of every type of message, Like so:

These 4 messages are possible candidates for the message with the highest priority.

Now we have to take time elapsed into consideration and increment accordingly. For this, we can ignore all the lesser priority messages that occur after the one we have already calculated. That is, we can skip message 3 and message 2 because message 4 will always be older and will have a higher increment.

We will only have to calculate it for 4 and 5.

Case 1: If 4 hasn’t spent a full 10 mins in the queue, the element to be popped out is 5

Case 2: If 4 has spent over 10 mins in the queue, the element to be popped out is 4. Even though the final values of both messages are equal, message 4 is popped out because it is ahead of message 5 in the linked list.

Once a certain message type is pushed out, the pointer is moved to the next occurrence of that message type.