3885. Design Event Manager

Description

You are given an initial list of events, where each event has a unique eventId and a priority.

Implement the EventManager class:

EventManager(int[][] events) Initializes the manager with the given events, where events[i] = [eventId_i, priority_i].
void updatePriority(int eventId, int newPriority) Updates the priority of the active event with id eventId to newPriority.
int pollHighest() Removes and returns the eventId of the active event with the highest priority. If multiple active events have the same priority, return the smallest eventId among them. If there are no active events, return -1.

An event is called active if it has not been removed by pollHighest().

Example 1:

Input:
["EventManager", "pollHighest", "updatePriority", "pollHighest", "pollHighest"]
[[[[5, 7], [2, 7], [9, 4]]], [], [9, 7], [], []]

Output:
[null, 2, null, 5, 9]

Explanation

EventManager eventManager = new EventManager([[5,7], [2,7], [9,4]]); // Initializes the manager with three events
eventManager.pollHighest(); // both events 5 and 2 have priority 7, so return the smaller id 2
eventManager.updatePriority(9, 7); // event 9 now has priority 7
eventManager.pollHighest(); // remaining highest priority events are 5 and 9, return 5
eventManager.pollHighest(); // return 9

Example 2:

Input:
["EventManager", "pollHighest", "pollHighest", "pollHighest"]
[[[[4, 1], [7, 2]]], [], [], []]

Output:
[null, 7, 4, -1]

Explanation

EventManager eventManager = new EventManager([[4,1], [7,2]]); // Initializes the manager with two events
eventManager.pollHighest(); // return 7
eventManager.pollHighest(); // return 4
eventManager.pollHighest(); // no events remain, return -1

Constraints:

1 <= events.length <= 10⁵
events[i] = [eventId, priority]
1 <= eventId <= 10⁹
1 <= priority <= 10⁹
All the values of eventId in events are unique.
1 <= newPriority <= 10⁹
For every call to updatePriority, eventId refers to an active event.
At most 10⁵ calls in total will be made to updatePriority and pollHighest.

Solutions

Solution 1: Sorted Set

Thinking

Poll the highest-priority live event, breaking ties by smallest \(\textit{eventId}\), and support priority updates. Up to \(10^5\) operations.

The max is an ordered-set endpoint; an update must erase the old key and insert the new one.

Store \((-\textit{priority},\textit{eventId})\) so higher priority and smaller id come first, and a hash map remembers the current priority for deletion.

A poll also drops the hash entry.

We define a sorted set \(\textit{sl}\) to store tuples of priority and id \((-\textit{priority}, \textit{eventId})\) for all active events, and a hash map \(\textit{d}\) to store the priority of each event.

During initialization, we iterate over the given event list, add the tuple of priority and id for each event into the sorted set \(\textit{sl}\), and store each event's priority in the hash map \(\textit{d}\).

For the \(\textit{updatePriority}(eventId, newPriority)\) operation, we first retrieve the old priority of the event from the hash map \(\textit{d}\), then remove the tuple of the old priority and event id from the sorted set \(\textit{sl}\), add the tuple of the new priority and event id into \(\textit{sl}\), and update the event's priority in \(\textit{d}\).

For the \(\textit{pollHighest}()\) operation, we first check whether the sorted set \(\textit{sl}\) is empty. If it is, return -1. Otherwise, we retrieve the event with the highest priority (i.e., the first element) from \(\textit{sl}\), remove its tuple, delete the event's priority information from \(\textit{d}\), and return the event's id.

In terms of time complexity, initialization takes \(O(n \log n)\) time, where \(n\) is the number of initial events. Each call to \(\textit{updatePriority}\) and \(\textit{pollHighest}\) takes \(O(\log n)\) time. The space complexity is \(O(n)\), where \(n\) is the number of active events.

Python3JavaC++Go

class EventManager:

    def __init__(self, events: list[list[int]]):
        self.sl = SortedList()
        self.d = {}
        for eventId, priority in events:
            self.sl.add((-priority, eventId))
            self.d[eventId] = priority

    def updatePriority(self, eventId: int, newPriority: int) -> None:
        old_priority = self.d[eventId]
        self.sl.remove((-old_priority, eventId))
        self.sl.add((-newPriority, eventId))
        self.d[eventId] = newPriority

    def pollHighest(self) -> int:
        if not self.sl:
            return -1
        eventId = self.sl.pop(0)[1]
        self.d.pop(eventId)
        return eventId


# Your EventManager object will be instantiated and called as such:
# obj = EventManager(events)
# obj.updatePriority(eventId,newPriority)
# param_2 = obj.pollHighest()

class EventManager {
    private TreeSet<int[]> sl;
    private Map<Integer, Integer> d;

    public EventManager(int[][] events) {
        sl = new TreeSet<>((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        d = new HashMap<>();
        for (int[] e : events) {
            int eventId = e[0], priority = e[1];
            sl.add(new int[] {-priority, eventId});
            d.put(eventId, priority);
        }
    }

    public void updatePriority(int eventId, int newPriority) {
        int old = d.get(eventId);
        sl.remove(new int[] {-old, eventId});
        sl.add(new int[] {-newPriority, eventId});
        d.put(eventId, newPriority);
    }

    public int pollHighest() {
        if (sl.isEmpty()) {
            return -1;
        }
        int[] top = sl.pollFirst();
        int eventId = top[1];
        d.remove(eventId);
        return eventId;
    }
}

/**
 * Your EventManager object will be instantiated and called as such:
 * EventManager obj = new EventManager(events);
 * obj.updatePriority(eventId,newPriority);
 * int param_2 = obj.pollHighest();
 */

class EventManager {
public:
    set<pair<int, int>> sl;
    unordered_map<int, int> d;

    EventManager(vector<vector<int>>& events) {
        for (auto& e : events) {
            int eventId = e[0], priority = e[1];
            sl.insert({-priority, eventId});
            d[eventId] = priority;
        }
    }

    void updatePriority(int eventId, int newPriority) {
        int old = d[eventId];
        sl.erase({-old, eventId});
        sl.insert({-newPriority, eventId});
        d[eventId] = newPriority;
    }

    int pollHighest() {
        if (sl.empty()) {
            return -1;
        }
        auto it = sl.begin();
        int eventId = it->second;
        sl.erase(it);
        d.erase(eventId);
        return eventId;
    }
};

/**
 * Your EventManager object will be instantiated and called as such:
 * EventManager* obj = new EventManager(events);
 * obj->updatePriority(eventId,newPriority);
 * int param_2 = obj->pollHighest();
 */

import (
    rbt "github.com/emirpasic/gods/v2/trees/redblacktree"
    "cmp"
)

type pair struct{ p, id int }

type EventManager struct {
    sl *rbt.Tree[pair, struct{}]
    d  map[int]int
}

func Constructor(events [][]int) EventManager {
    sl := rbt.NewWith[pair, struct{}](func(a, b pair) int {
        return cmp.Or(a.p-b.p, a.id-b.id)
    })
    d := make(map[int]int)

    for _, e := range events {
        eventId, priority := e[0], e[1]
        sl.Put(pair{-priority, eventId}, struct{}{})
        d[eventId] = priority
    }

    return EventManager{sl: sl, d: d}
}

func (this *EventManager) UpdatePriority(eventId int, newPriority int) {
    old := this.d[eventId]
    this.sl.Remove(pair{-old, eventId})
    this.sl.Put(pair{-newPriority, eventId}, struct{}{})
    this.d[eventId] = newPriority
}

func (this *EventManager) PollHighest() int {
    if this.sl.Size() == 0 {
        return -1
    }
    it := this.sl.Iterator()
    it.First()

    top := it.Key()
    eventId := top.id

    this.sl.Remove(top)
    delete(this.d, eventId)

    return eventId
}

/**
 * Your EventManager object will be instantiated and called as such:
 * obj := Constructor(events);
 * obj.UpdatePriority(eventId,newPriority);
 * param_2 := obj.PollHighest();
 */

3885. Design Event Manager

Description

Solutions

Solution 1: Sorted Set

Comments