Problem Statement in English

You’re given a list of events, where each event is represented as a pair of integers [e, p], where e is the event’s unique identifier and p is its priority. You need to design an event manager that supports the following operations:

  1. updatePriority(e, np): Update the priority of the event with identifier e to np.
  2. pollHighest(): Remove and return the identifier of the event with the highest priority.

If there are multiple events with the same highest priority, return the one with the smallest identifier. If there are no events, return -1.

Approach

To solve this problem, we can use a data structure that allows us to maintain the events in sorted order based on their priority and identifier. A good choice for this is a SortedList from the sortedcontainers library in Python.

We will maintain a SortedList of events, where each event is stored as a tuple (priority, identifier). This way, the events will be automatically sorted first by priority (in descending order) and then by identifier (in ascending order). We will also maintain a dictionary to keep track of the current priority of each event for efficient updates.

When we need to update the priority of an event, we will remove the old entry from the SortedList and add a new entry with the updated priority. When we need to poll the highest priority event, we can simply pop the last element from the SortedList, which will be the event with the highest priority.

And we’re done!

Solution in Python


class EventManager:

    def __init__(self, events: list[list[int]]):
        self.l = SortedList(key=lambda x: (x[0], -x[1]))
        self.db = {}

        for e, p in events:
            self.l.add((p, e))
            self.db[e] = p

    def updatePriority(self, e: int, np: int) -> None:
        p = self.db[e]
        index = self.l.index((p, e))

        self.l.pop(index)
        self.l.add((np, e))
        self.db[e] = np        

    def pollHighest(self) -> int:
        if not self.l:
            return -1

        return self.l.pop()[1]

Complexity

  • Time: $O(n \log n)$
    Since we need to maintain the sorted list, each update and poll operation will take logarithmic time.

  • Space: $O(n)$
    Since we need to store all the events in the sorted list and the dictionary.

And we are done.